剑指offer刷题笔记——二进制中1的个数

题目描述

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

题目地址

https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8?tpId=13&tqId=11164&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

思路

• 位运算 - 移位计数

  • 时间复杂度：O(N)，N 为整型的二进制长度
  • 注意移位判断有两种方式：一是移动 n，一是移动"1"，后者更好
  • 当 n 为 负数时，移动 n 可能导致死循环

• 位运算 - 利用 n&(n-1)

  • 该运算的效果是每次除去 n 的二进制表示中最后一个 1

    n       : 10110100
    n-1     : 10110011
    n&(n-1) : 10110000
    

  • 时间复杂度：O(M)，M 为二进制中 1 的个数

Code - 移位计数

class Solution {
public:
     int NumberOf1(int n) {
         int ret = 0;
         int N = sizeof(int) * 8;
         while(N--) {
             if(n & 1)
                 ret++;
             n >>= 1;
         }
         return ret;
     }
};

Code - 移位计数（改进）

class Solution {
public:
     int NumberOf1(int n) {
         int ret = 0;
         int N = sizeof(int) * 8;
         int flag = 1;
         while(N--) {
             if(n & flag)
                 ret++;
             flag <<= 1;    // 移动 1 而不是 n
         }
         return ret;
     }
};

Code - n&(n-1)

class Solution {
public:
     int NumberOf1(int n) {
         int ret = 0;
         while(n) {
             ret++;
             n = (n-1)&n;
         }
         return ret;
     }
};