二进制中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));
	}
}