剑指offer_04_二进制中1的个数/整数1出现的次数

01_二进制中1的个数

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

解题思路

如果一个整数不为0，那么这个整数二进制中至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。
举个例子：一个二进制数1110，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1100.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

图片说明

java代码实现如下：*

public class Solution {
 public int NumberOf1(int n) {
     int count = 0;
     while(n!= 0){
         count++;
         n = n & (n - 1);
      }
     return count;
 }
}

02_整数1出现的次数

题目描述

求出1--13的整数中1出现的次数,并算出100--1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

解题思路

要统计1~n这n个数中1的个数，只需要统计出每个数字中1的个数即可。例如1116中有3个1 。将1116转化为字符串即Integer.toString()方法，再使用charAt()方法判断每个字符是否为字符1即可。

java代码实现如下：
```
public class Solution {
  public int NumberOf1Between1AndN_Solution(int n) {
  int flag = 0;
  for (int i = 1; i <= n; i++) {
      for (int j = 0; j <Integer.toString(i).length(); j++) {
      if (Integer.toString(i).charAt(j)=='1')
      flag++;
      }
  }
      return flag;
  }
} 
```
03_调整数组顺序使奇数位于偶数前面

题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
解题思路
解法一：遍历数组，比较arr[i]和arr[i-1],如果偶数位于奇数前面，则互相交换位置。交换后，再看arr[i-1]与arr[i-2]要不要交换，一直对比到arr[1]和arr0。于是，每次对比arr[i]之前的元素，一直到i=arr.length-1结束循环。
解法二：新建立一个数组arr1[arr.length]，长度与元素组相等。两个索引j 和k 分别从arr[0]和arr[arr.length-1]开始遍历数组。如果arr[j]为奇数，则放在数组的arr1[i]位置，如果是偶数则不处理。如果arr[k]为偶数，则放在数组的arr1[arr.length-1-i]位置，如果是奇数则不处理。直到arr[j]遍历到j==arr.length-1,并且arr[k]遍历到k==0.此时数组遍历完毕。

java代码实现如下：

public class Solution {
  public void reOrderArray(int [] array) {
      for (int i = 0; i < array.length; i++) {
      for (int j = i; j > 0; j--) {
      if (array[j - 1] % 2 == 0 && array[j] % 2 == 1) {
          int temp = array[j - 1];
          array[j - 1] = array[j];
          array[j] = temp;
      }
      }
   }
 }
}