NumberOf1Bits [source code]

public class NumberOf1Bits {
static
/******************************************************************************/
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int counter = 0;
        if ((n & 1) == 1) counter++;
        n = n >>> 1;
        while (n > 0) {
            n = n & (n - 1);
            counter++;
        }
        return counter;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        NumberOf1Bits.Solution tester = new NumberOf1Bits.Solution();
        int[] inputs = {11, 15, 10381040, Integer.MAX_VALUE};
        for (int i : inputs) {
            System.out.println(Integer.toBinaryString(i));
            System.out.printf("%d: expected: %d, output: %d %n", i, Integer.bitCount(i), tester.hammingWeight(i));
        }
    }
}

简单的方法肯定是一个按位的 loop, 不过有一个更快的方法, 还是参考以前那个eliminate rightmost 1bit的思路;

while loop 数数的方法

如果是 for loop, 那么数 iteration 的数量的时候就很简单, 直接找到 loop var 的range就行了;
那么 while 呢? while loop 没有一个明显的 loop var 的定义, 但是实际上这个方法是类似的; 比如这里, 我们的 header 里面就是一个 n, 那么你只要数一下 n 有多少个legitimate value就行了, 这个可取值的个数就是最后执行了的 iteration的个数;

另外还是要提醒一下, bit操作要加括号, 优先级非常低;

最后的速度居然只有2(15), 题目比较老了, 而且这里这个技巧也不是什么特别巧夺天工的技巧, 还是很多人能够想到的;

这里有一个小的插曲, 这个题目的要求是 unsigned, 所以这里暗示的一个坑就是他可能会出类似Integer.MAX_VALUE + 1这样的 case 来坑你; 我刚开始没有想到怎么弄, 后来想到一个办法, 就实现判断一下个位, 把个位记录下来, 然后整个 n 右移(用 unsigned shift), 然后这个值肯定就是一个用signed 32bit-int可以处理的值了;

这个是 submission 最优解:

public class Solution {  
    // you need to treat n as an unsigned value  
    public int hammingWeight(int n) {  
        int result = 0;  
        while (n != 0) {  
            result += n & 1;   
            n = n >>> 1;  
        }  
        return result;  
    }  
}

等于说实际上按位数反而是最快的. 想了想, 可能bit and并没有我想的那么快? 当然也有可能只是波动; 而且 right 1 的解法时间是O(number of 1bits), 普通移位的速度是O(number of all bits), 如果 oj 的 case 多数是1非常多的, 最后我们用 right 1的解法也未必就能让 OJ 觉得快很多;

这个是 wiki 上面的一些更优的解法, 有时间再看好了:

// This is a naive implementation, shown for comparison, and to help in understanding the better functions.   
// It uses 24 arithmetic operations (shift, add, and).  
int hammingWeight(uint32_t n)  
{  
    n = (n & 0x55555555) + (n >>  1 & 0x55555555); // put count of each  2 bits into those  2 bits   
    n = (n & 0x33333333) + (n >>  2 & 0x33333333); // put count of each  4 bits into those  4 bits   
    n = (n & 0x0F0F0F0F) + (n >>  4 & 0x0F0F0F0F); // put count of each  8 bits into those  8 bits   
    n = (n & 0x00FF00FF) + (n >>  8 & 0x00FF00FF); // put count of each 16 bits into those 16 bits   
    n = (n & 0x0000FFFF) + (n >> 16 & 0x0000FFFF); // put count of each 32 bits into those 32 bits   
    return n;  
}  

// This uses fewer arithmetic operations than any other known implementation on machines with slow multiplication.  
// It uses 17 arithmetic operations.  
int hammingWeight(uint32_t n)  
{  
    n -= (n >> 1) & 0x55555555; //put count of each 2 bits into those 2 bits  
    n = (n & 0x33333333) + (n >> 2 & 0x33333333); //put count of each 4 bits into those 4 bits  
    n = (n + (n >> 4)) & 0x0F0F0F0F; //put count of each 8 bits into those 8 bits  
    n += n >> 8; // put count of each 16 bits into those 8 bits  
    n += n >> 16; // put count of each 32 bits into those 8 bits  
    return n & 0xFF;  
}  

// This uses fewer arithmetic operations than any other known implementation on machines with fast multiplication.  
// It uses 12 arithmetic operations, one of which is a multiply.  
int hammingWeight(uint32_t n)  
{  
    n -= (n >> 1) & 0x55555555; // put count of each 2 bits into those 2 bits  
    n = (n & 0x33333333) + (n >> 2 & 0x33333333); // put count of each 4 bits into those 4 bits  
    n = (n + (n >> 4)) & 0x0F0F0F0F; // put count of each 8 bits into those 8 bits   
    return n * 0x01010101 >> 24; // returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24)  
}

Problem Description

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Difficulty:Easy
Category:Algorithms
Acceptance:39.35%
Contributor: LeetCode
Companies
microsoft apple
Related Topics
bit manipulation
Similar Questions
Reverse Bits Power of Two Counting Bits Binary Watch Hamming Distance