二进制中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 很多二进制的问题都可以用这种思路解决，

左移和右移

左移运算符 m << n 表示把 m 左移 n 位。在左移n 位的时候，最左边的 n位将被丢弃，同时在最右边补上n个 0.比如：

00001010<<2=00101000

10001010<<3=01010000

右移运算符m>>n表示把m右移n位。在右移n位的时候,最右边的。

n位将被丢弃。但右移时处理最左边位的情形要稍微复杂一点。如果数字是一个无符号数值,则用0填补最左边的n位;如果数字是一个有符号数值,则用数字的符号位填补最左边的n位。也就是说,如果数字原先是一个正数,则右移之后在最左边补n个0:如数字原先是负数,则右移之后在最左边补n个1下面是对两个8位有符号数进行右移的例子:

00001010>>2=00000010

10001010>>3=11110001

1、基本都是参考别的博客和书本的代码,仅作为自己笔记用!!

1、<<:左移运算符,num<<1相当于num乘以2

>>:右移运算符,num>>1,相当于num除以2

>>>:无符号右移,忽略符号位,空位都以0补齐

2、与1位与得1就是奇数,1只有最后一位是1

题目

输入一个整数，输出该数二进制表示中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;
}

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