剑指offer（第二版）——二进制中1的个数

PS：《剑指offer》是很多同学找工作都会参考的一本面试指南，同时也是一本算法指南（为什么它这么受欢迎，主要应该是其提供了一个循序渐进的优化解法，这点我觉得十分友好）。现在很多互联网的算法面试题基本上可以在这里找到影子，为了以后方便参考与回顾，现将书中例题用Java实现（第二版），欢迎各位同学一起交流进步。

GitHub： https://github.com/Uplpw/SwordOffer。

完整题目链接： https://blog.csdn.net/qq_41866626/article/details/120415258

1 题目描述

实现一个函数，输入一个int型整数，输出该数字在计算机中二进制表示形式的1的个数。
例如9->1001,输出2；-3->11111111111111111111111111111101,输出31。

leetcode链接： 二进制中1的个数（以下代码已测试，提交通过）

2 测试用例

一般是考虑功能用例，特殊（边缘）用例或者是反例，无效测试用例这三种情况。甚至可以从测试用例寻找一些规律解决问题，同时也可以让我们的程序更加完整鲁棒。

（1）功能用例：正常的n值，有正有负。

（2）边缘用例：0。

（3）无效用例：无。

3 思路

分析：

本题考查位运算，要注意负数的处理。

首先要明确计算机中，数字是以补码的形式存储的。

其次，明确位运算符以及其优先级，与 &，或 |，非~，异或 ^，<<左移位，>> 有符号右移位，>>> 无符号右移位(java有此符号，c++没有)

下面是几种解法过程。

• 解法一：将数字无符号右移，判断最右边的为是否1，直到为0。
• 解法二：使用一个标记，初始为1，让标记值与原输入数字进行与操作，然后标记值左移。
• 解法三：对于二进制数有如下结论：【把一个整数减去1之后再和原来的整数做位与运算，得到的结果相当于把原整数的二进制表示形式的最右边的1变成0】。因此只需要累计多少次该操作后，该数字为0即可。比如1001，执行一次上述结论，1001 & 1000=1000，将最右边的1改为了0；再执行一次，1000 & 0111=0000，第二个1也改成了0。因此能执行几次该结论，就有几个1。对于解法1、2，都需要循环32次，判断每一个比特位是否为1，而解法三，循环次数等于比特位为1的个数。时间上是有改进的。

4 代码

算法实现：

public class NumberOf1InBinary {
    // 解法1：无符号右移 >>>，与1进行与操作，返回不为0即为1
    public static int numberOfOne1(int n) {
        int count = 0;
        while (n != 0) {
            if ((n & 1) != 0) {
                count++;
            }
            n >>>= 1;
        }
        return count;
    }

    // 解法2：有符号左移 << ，和 1 做与操作，判断结果是否为1，并将标志左移 <<
    public static int numberOfOne2(int n) {
        int count = 0;
        int flag = 1;
        while (flag != 0) {
            if ((n & flag) != 0) {
                count++;
            }
            flag <<= 1;
        }
        return count;
    }

    // 解法3：把一个整数减去 1 后再与其做与运算，相当于把整数的二进制最右边的 1 变成 0
    public static int numberOfOne3(int n) {
        int count = 0;
        while (n != 0) {
            // 注意 & 的优先级比较低，需要使用括号
            n &= (n - 1);
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println("正数");
        System.out.println(numberOfOne1(3));
        System.out.println(numberOfOne2(3));
        System.out.println(numberOfOne3(3));
        System.out.println("负数");
        System.out.println(numberOfOne1(-3));
        System.out.println(numberOfOne2(-3));
        System.out.println(numberOfOne3(-3));
    }
}

5 举一反三

1. 问题：使用一条语句判断一个正整数是不是2的整数次方 。

思路：2的整数次方二进制只有一个1，减去1后再与其做与运算结果为0

代码：

public static boolean isPowerOfTwo(int n){
    return (n&(n-1))==0;
}

2. 问题：输入两个整数m，n，计算最少需要改变m的多少位才能得到n 。

思路：先对m，n进行异或（计算不同位的个数），再统计异或结果中1的位数

代码：

public static int changeMToN(int m, int n){
    int m=^n;
    int count = 0;
    while (m != 0) {
        // 注意 & 的优先级比较低，需要使用括号
        m &= (m - 1);
        count++;
    }
    return count;
}

参考
在解决本书例题时，参考了一些大佬的题解，比如leetcode上的官方、K神，以及其他的博客，在之后的每个例题详解后都会给出参考的思路或者代码链接，同学们都可以点进去看看！

本例题参考：
https://www.jianshu.com/p/33d4b952f445

本文如有什么不足或不对的地方，欢迎大家批评指正，最后希望能和大家一起交流进步、拿到心仪的 offer !!!