位运算
1. 获取数字 n的二进制的第 k位是多少
步骤
- 先将二进制数向右移动 k位(此时 k位移动到了第一位), 操作:
x >> k
- 获取最后一位的值, 操作:
移动后的值 & 1
- 两步和为一步操作:
x >> k & 1
获取 n的二进制
代码
for (int i = n; i >= 0; i--) {
System.out.print(x >> i & 1);
}
2. lowBit
返回 x的二进制数的最后为 1的后面的数
如 100100返回 100, 十进制直接返回十进制
题目26
代码
class Solution {
public int NumberOf1(int n) {
int res = 0;
while (n != 0) {
n -= lowBit(n); // 减去并记录
res++;
}
return res;
}
private int lowBit(int x) {
return x & -x;
}
}
题目 801
与题目26完全相同
代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 对输入数据进行初始化
Scanner in = new Scanner(System.in);
int n = in.nextInt();
// n次输出
while (n-- > 0) {
int target = in.nextInt();
int res = 0;
while (target != 0) {
target -= (target & -target); // 十进制进行计算
res++;
}
System.out.print(res + " ");
}
}
}
补充
-
原码: 数字 n的二进制
如: 10的原码:1010
* 反码: 将原码取反如: 10的反码:0101
* 补码: 反码 +1如: 10的反码:0110
总结
- 求 n的第 k位数字:
n >> k & 1
- 返回 n的最后一位 1:
lowbit(n) = n & -n
求 n的第 k位数字: 为什么不是右移k-1位呢
针牛蛙
学习了,多谢大神的分享