最近招了一个 42岁的程序员，薪资只给了不到15000，比刚毕业两三年的小年轻还便宜。。

算法题：位1的个数

这个题目，名字就透着一股“我不复杂但你得细心”的气质：“位1的个数”。看上去挺简单的，不就是数一个整数里有几个1么？是的，题意就是这么朴素，但你要是用暴力法直接上，那真是太“暴力”了点...

最开始我确实这么干的，直接把整数转成二进制字符串，然后用charAt()遍历计数。你猜怎么着？面试官笑而不语😅。因为这思路太耿直了，根本不配叫“位运算”题——明明考你的是对“位”的理解和操作嘛。

于是开始研究那些“高手写法”。最经典的其实是Brian Kernighan那套——听起来像某个计算机科学家，其实也真是。他写了个算法专门干这个事，而且还非常高效。

大概长这样：

publicinthammingWeight(int n){
int count = 0;
while (n != 0) {
        n &= (n - 1); // 每次消掉最右边的1
        count++;
    }
return count;
}

这个代码里的魔法操作是 n &= (n - 1)，这句话的意思是：每次都把当前最右边的1给“抹掉”，直到没有1为止。每抹掉一次，就计数一次。牛不牛？而且这个算法的时间复杂度是 O(k)，k 是这个整数中1的个数。

讲真，这个技巧我第一次看到的时候，内心是震撼的。原来位运算还能这么玩？对比起我那种把整型转成字符串，然后用循环数字符的写法，这种真的是程序员该有的样子 🤓。

当然，Java里也贴心到家，直接给你内置好了：

Integer.bitCount(n);

没错，这就一行，就搞定了。但你敢在面试时候直接这么写，面试官十有八九得问你：“如果系统不支持这个方法你怎么办？”——这时候你要是刚好记得 n &= (n - 1) 这个小技巧，那就稳了 ✌️。

顺便提一下负数的问题。在Java里，整型是用补码表示的。所以如果你想从负数里数1的个数，直接用上面那两个方法都是OK的。Integer.bitCount直接支持，n &= (n - 1)也能顺利处理，因为它操作的就是位，不关心正负。但如果你脑抽写成这样：

Integer.toBinaryString(n).chars().filter(c -> c == '1').count();

那可就不一定对了，因为 toBinaryString 对负数会输出补码对应的二进制，不带符号位前缀，会误导你。面试时候别翻车。

哦对了，还有个坑，就是循环终止条件。你如果用了：

while (n > 0)

那在面对负数的时候就会直接GG，因为负数的补码里1可能比你想象的多，你得用 n != 0 才能跑完所有的1。

所以，下次面试碰上这种“数位1”的题，别急着写代码，先问问自己：我要不要再低一层？要不要用“Brian Kernighan”？再不济，也别忘了那个 Integer.bitCount() 😏

你们觉得呢？面试里，写简洁还是写“技术含量高”的重要？欢迎来掰扯掰扯