【剑指offer】面试题15：二进制中1的个数

客官°小女子只卖身不卖艺 2022-06-12 08:22 175阅读 0赞

## 完整代码地址 ##

[完整代码地址][Link 1]

## 题目 ##

请实现一个函数，输入一个整数，输出该数二进制表示中1的个数，其中负数用补码表示。例如，把9表示成二进制是1001，有2位是1。因此，如果输入9，则该函数输出2。

## 思路 ##

**解法1（循环32次）**  
输入一个int型的整数，int是32位的  
将这个数每次右移一位，与1做与操作  
一共右移32次，即可得到答案

**解法2（循环1的个数次）**  
把一个整数减去1，再和原整数做与运算，会把改整数最右边的1变成0。  
例如：  
1.一个八位的二进制数00001100，它减去1，得到00001011，做与运算后得到00001000。  
2.一个八位的二进制数00001101，它减去1，得到00001100，做与操作后得到00001100。  
**负数也是一样的**  
3.一个八位的二进制数11110110，即-10，它减去1，得到11110101，即-11，做与操作后得到11110100。

## 代码（解法1） ##

public static int NumberOf1(int n) {
        int count = 0;
        for(int i = 0; i < 32; ++i) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }

## 更加效率的解法（解法2） ##

/**
     * 惊喜的解法
     * 只需要循环1的个数次
     */
    public static int MagicNumberOf1(int n) {
        int count = 0;
        while(n != 0) {
            int tmp = n - 1;
            n &= tmp;
            ++count;
        }
        return count;
    }

## 测试 ##

public static void main(String[] args) {
        test1();
        test2();
    }
    
    /**
     * 功能测试
     */
    private static void test1() {
        int count = _15_NumberOf1InBinary.NumberOf1(5);
        MyTest.equal(count, 2);
    
        count = _15_NumberOf1InBinary.NumberOf1(-65);
        MyTest.equal(count, 31);
    }
    
    /**
     * 边界测试
     * 1. Integer.MAX_VALUE
     * 2. Integer.MIN_VALUE
     * 3. 0
     * 4. 1
     * 5. -1
     */
    private static void test2() {
        int count = _15_NumberOf1InBinary.NumberOf1(Integer.MAX_VALUE);
        MyTest.equal(count, 31);
    
        count = _15_NumberOf1InBinary.NumberOf1(Integer.MIN_VALUE);
        MyTest.equal(count, 1);
    
        count = _15_NumberOf1InBinary.NumberOf1(0);
        MyTest.equal(count, 0);
    
        count = _15_NumberOf1InBinary.NumberOf1(1);
        MyTest.equal(count, 1);
    
        count = _15_NumberOf1InBinary.NumberOf1(-1);
        MyTest.equal(count, 32);
    }

[Link 1]: https://github.com/linpeiyou/CodingInterviews