Loading... # Brian Kernighan 算法 对任何一个数 `n` ，`n & ( n − 1 )` 的结果是`n` 的比特位最右端的 1 变为 0 的结果，可以用于清除二进制数中最右侧的 1。 例如： n = 12 Dec = 1**1**00 Bin n - 1 = 11 Dec = 1011 Bin n & (n - 1) = 1**0**00 Bin `n & (~n + 1)`提取出整数 `n` 最后一位为 1 的数 n = 12 Dec = 1**1**00 Bin ~n = 0011 Bin, ~n + 1 = 0100 Bin n & (~n + 1) = 0**1**00 ## 用例 LeetCode338 比特位计数 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。 ```java public int[] countBits(int n) { int[] arr = new int[n + 1]; for (int i = 1; i < n + 1; i++) { arr[i] = countOnes(i); } return arr; } private int countOnes(int num) { int ones = 0; while (num > 0) { num &= (num - 1); ones++; } return ones; } ``` 最后修改：2023 年 01 月 15 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 本作品采用 CC BY-NC-SA 4.0 International License 进行许可。
