二进制中1的个数

题目描述

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

解决方法

  • bitCount(int i)

    这是Integer源码中的一个方法,就是返回i的补码中1的个数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public static int bitCount(int i) {
    // 每两位存储每两位值为1的个数。
    i = i - ((i >>> 1) & 0x55555555);
    // 每四位存储每四位值为1的个数。
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    // 每八位存储每八位值为1的个数。
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    // 每十六位存储每十六位值为1的个数。
    i = i + (i >>> 8);
    // 每三十二位存储每三十二位值为1的个数。
    i = i + (i >>> 16);
    // 由于值最大为32,所以只关注后六位即可。
    return i & 0x3f;
    }
  • n = n & (n-1)

    一个二进制只要不为0,一定有一位是1。一个二进制数减1,如果最后一位为1,那么最后一位变为0,其他位不变,如果最后一位为0,那么最后一位变为1,其上一位如果为0则变1,再上一位如果为1则变0,直到遇到为1的位变0,其他位不变。即二进制数减1就是从右到左的第一个1变为补码,其余位数不变。二进制与其减1进行与操作,就是将最右边的1变为0的结果,所以二进制可以做多少次这样的操作,就是二进制中有一个1。

    1
    2
    3
    4
    5
    6
    7
    8
    public int NumberOf1(int n) {
    int count = 0;
    while (n != 0) {
    count++;
    n = n & (n - 1);
    }
    return count;
    }
-------------本文结束感谢您的阅读-------------

本文标题:二进制中1的个数

文章作者:huihui

发布时间:2018年11月04日 - 00:11

最后更新:2019年02月14日 - 19:02

原始链接:http://101.200.47.120:8011/2018/11/04/二进制中1的个数/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。