11 剑指offer--位运算--二进制中1的个数

二进制中1的个数

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

基础知识

位运算是把数字用二进制表示之后，对每一位上0 或者 I 的运算。二进制及其位运算是现代计算机学科的基石，很多底层的技术都离不开位运算，因此与位运算相关的题目也经常出现在面试中。我们在日常生活中习惯了十进制，很多人看到二进制及位运算都觉得很难适应。

理解位运算的第一步是理解二进制。二进制是指数字的每一位都是0或者I。比如十进制的2 转换成二进制之后是10,而十进制的10转换成二进制之后是1010。在程序员圈子里有一则流传了很久的笑话，说世界上有10种人，一种人知道二进制，而另一种人不知道二进制 ...

在微软产品Excel中，用 A 表示第1 列，B 表示第2 列……Z 表示第26列，AA表示第27列，AB表示第28列……以此类推。请写出一个函数，输入用字母表示的列号编码，输出它是第几列。

这是一道很新颖的关于进制的题目，其本质是把十进制数字用A〜Z表示成二十六进制。如果想到这一点，那么解决这个问题就不难了。其实二进制的位运算并不是很难掌握，因为位运算总共只有5 种运算:与、或、异或、左移和右移。与、或和异或运算的规律我们可以用表2.1总结如下。

把一个整数减去 1 之后再和原来的整数做位与运算，得到的结果相当于把整数的二进制表示中最右边的1变成0 很多二进制的问题都可以用这种思路解决，

左移和右移

题目

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

思路：最简单的思路，整数n每次进行无符号右移一位，同1做&运算，可以判断最后以为是否为1。

通常的剑指offer的思路，n&(n-1) 操作相当于把二进制表示中最右边的1变成0。所以只需要看看进行了多少次这样的操作即可。看看什么时候n为0.

思路1：

先判断二进制表示的最右1位是不是1，把整数和1做与运算即可，然后右移一位，再判断，直到整数变为0。

把整数右移一位和把整数除以2在数学上是等价的但是位运算效率最高，但是思路1可能会陷入死循环，如输入一个负数0x8000，右移之后并不是0x4000，而是0xC000，因为负数移位后要补1，如果循环下去会变成0xFFFF。

思路2：

为了避免死循环就要避免右移，我们首先把数字和1做与运算，判断它最低位是不是1，接着把1左移一位得到2，在和输入数与运算，节能判断次低位是不是1，反复左移即可。

#include<iostream>

using namespace std;
int NumberOf1(int n)//有符号的n
{
    int count=0;
    int flag=1;
    while (flag)
    {
        if (n&flag)
        {
            count++;
        }
        flag=flag<<1;//左移一位
    }  
    return count;
}
int main()
{
    cout<<NumberOf1(9)<<endl;//1001
    cout<<NumberOf1(15)<<endl;//1111
    return 0;
}

思路3

思路2中输入的数的二进制表示有几位，程序就会循环多少次，改进的思路3是二进制里有几个1就循环几次。首先记住一个常用做法：把一个整数减去1之后再和原来的整数做位与运算，得到的结果相当于把整数二进制表示中的最右边一个1变成0。基于上述做法，一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。

public class NumberOf1 {
	static Integer numberof1(int number){
		int count = 0;
		while(number != 0){
			number = (number - 1) & number;
			count++;
		}
		return count;
	}
	public static void main(String[] args){
		System.out.println(numberof1(10));
	}
}

LeetCode

位1的个数

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

示例 1：

输入：00000000000000000000000000001011

输出：3

解释：输入的二进制串 00000000000000000000000000001011 ***有三位为 '1'。

示例 2：

输入：00000000000000000000000010000000

输出：1

解释：输入的二进制串 00000000000000000000000010000000 ***有一位为 '1'。

示例 3：

输入：11111111111111111111111111111101

输出：31

解释：输入的二进制串 11111111111111111111111111111101 ***有 31 位为 '1'。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。

在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的示例 3 中，输入表示有符号整数 -3。

进阶:

如果多次调用这个函数，你将如何优化你的算法？

public static void main(String[] args) {
    System.out.println("请输入一个整数");
    Scanner sc = new Scanner(System.in);
    System.out.println(sc.nextInt());

}

public static int hammingWeight(int n) {
    int num =0;
    String s = Integer.toBinaryString(n);
    for (int i = 0; i <s.length() ; i++) {
        if(s.charAt(i) =='1'){
            ++num;
        }
    }
    return num;
}

相关问题

判断一个整数是不是2的整数次方
分析：一个整数如果是2的正数次方，那么这个正数的二进制位中只有一个1；
只需要一句语句就可以判断：假设这个正数为n:只需判断n&(n-1)是否为0；
#include<iostream>
using namespace std;
bool fun(int n)
{
    if (n&n-1)
    {
        return false;
    }
    return true;
}
int main()
{
    cout<<fun(1)<<endl;
    cout<<fun(2)<<endl;
    cout<<fun(8)<<endl;
    cout<<fun(10)<<endl;
    return 0;
}

输入两个整数m和n,计算需要改变m二进制中的多少位才能得到n;
如：10:1010；13:1101，则需要改变10的二进制的后三位才能得到1101；
解决思路是，先求这两个数的异或，然后统计异或结果中1的个数。
public class NumberOf1 {
	static Integer numberof1(int number){
		int count = 0;
		while(number != 0){
			number = (number - 1) & number;
			count++;
		}
		return count;
	}
	public static void main(String[] args){
		System.out.println(numberof1(10));
	}
}