Open LLwanran opened 5 years ago
解法一 利用整数 1,依次左移每次与 n 进行与运算,若结果不为0,说明这一位上数字为 1,++cnt。
此解法 i 需要左移 32 次。
不要用 n 去右移并与 1 进行与运算,因为 n 可能为负数,右移时会陷入死循环。
function Solution(n) { let i = 1; let cnt = 0; while (i != 0) { if ((n & i) != 0) { ++cnt; } i <<= 1; } return cnt; }
解法二(推荐) 运算(n - 1) & n,直至 n 为 0。运算的次数即为 n 的二进制中 1 的个数。
(n - 1) & n
因为 n-1 会将 n 的最右边一位 1 改为 0,如果右边还有 0,则所有 0 都会变成 1。结果与 n 进行与运算,会去除掉最右边的一个 1。
举个栗子:
若 n = 1100, n - 1 = 1011 n & (n - 1) = 1000 即:把最右边的 1 变成了 0。
把一个整数减去 1 之后再和原来的整数做位与运算,得到的结果相当于把整数的二进制表示中最右边的 1 变成 0。很多二进制的问题都可以用这种思路解决。
function Solution(n) { let cnt = 0; while (n != 0) { ++cnt; n &= (n - 1); } return cnt; }
解法一 利用整数 1,依次左移每次与 n 进行与运算,若结果不为0,说明这一位上数字为 1,++cnt。
此解法 i 需要左移 32 次。
不要用 n 去右移并与 1 进行与运算,因为 n 可能为负数,右移时会陷入死循环。
解法二(推荐) 运算
(n - 1) & n
,直至 n 为 0。运算的次数即为 n 的二进制中 1 的个数。因为 n-1 会将 n 的最右边一位 1 改为 0,如果右边还有 0,则所有 0 都会变成 1。结果与 n 进行与运算,会去除掉最右边的一个 1。
举个栗子: