算法训练-位运算
位运算
leetcode191. 位1的个数
191. 位1的个数
https://leetcode.cn/problems/number-of-1-bits/
法一：巧用n&(n-1)
public class Method01 {
public int hammingWeight(int n) {
int count = 0; // 初始化计数器，用于记录'1'的数量
// 当 n 不为 0 时继续循环
while (n != 0) {
n &= (n - 1); // 将 n 最右边的 '1' 置为 '0'
count++; // 计数器加一
}
return count; // 返回汉明重量
}
}法二：逐位判断
public class Method02 {
public int hammingWeight(int n) {
int count = 0; // 初始化计数器，用于记录'1'的数量
// 当 n 不为 0 时继续循环
while (n != 0) {
count += n & 1; // 通过与运算获取 n 最右边的位，如果为 1 则 count 加 1
n >>= 1; // 右移 n，准备检查下一个位
}
return count; // 返回汉明重量
}
}leetcode231. 2 的幂
231. 2 的幂https://leetcode.cn/problems/power-of-two/
法一：二进制的表示
public class Method01 {
public boolean isPowerOfTwo(int n) {
// 检查 n 是否小于或等于 0， 如果是则不是 2 的幂
if (n <= 0) {
return false;
}
// 检查 n 是否为 2 的幂，使用位与运算：2 的幂具有唯一一个 '1' 位
return (n & (n - 1)) == 0;
}
}leetcode371. 两整数之和
371. 两整数之和https://leetcode.cn/problems/sum-of-two-integers/
法一：位运算
public class Method01 {
public int getSum(int a, int b) {
int c = 0; // 初始化 c，用于存储进位
// 当 b 不为 0 时，继续进行加法运算
while (b != 0) {
c = a & b; // 计算进位部分，使用位与运算
a = a ^ b; // 计算和部分，不考虑进位，使用位异或运算
b = c << 1; // 将进位左移一位，以便加到下一高位
}
return a; // 返回最终的和
}
}leetcode136. 只出现一次的数字
136. 只出现一次的数字https://leetcode.cn/problems/single-number/
法一：位运算
public class Method01 {
public int singleNumber(int[] nums) {
int a = 0; // 初始化变量a为0，用于存储结果
// 遍历数组中的每一个数字
for (int i = 0; i < nums.length; i++) {
a = a ^ nums[i]; // 使用异或运算更新a
}
// 返回只出现一次的数字
return a;
}
}leetcode137. 只出现一次的数字 II
137. 只出现一次的数字 IIhttps://leetcode.cn/problems/single-number-ii/
法一：有限状态自动机
public class Method01 {
// 方法：找到只出现一次的数字，其他数字均出现三次
public int singleNumber(int[] nums) {
// 初始化：ones 表示当前只出现一次的数字的位状态
int ones = 0;
// 初始化：twos 表示当前出现两次的数字的位状态
int twos = 0;
// 遍历输入数组中的每个数字
for (int num : nums) {
// 更新 ones：在 num 还未在 twos 中的情况下更新
// 具体逻辑为：ones = (ones ^ num) 仅在 num 不在 twos
ones = ones ^ num & ~twos;
// 更新 twos：在 num 还未在 ones 中的情况下更新
// 具体逻辑为：twos = (twos ^ num) 仅在 num 不在 ones
twos = twos ^ num & ~ones;
}
// 返回结果：ones 中存储的就是只出现一次的数字
return ones;
}
}法二：遍历统计
public class Method02 {
// 方法：找到只出现一次的数字，其他数字均出现三次
public int singleNumber(int[] nums) {
// 创建一个数组 counts，用于统计每个位上 1 的出现次数
int[] counts = new int[32];
// 遍历输入数组中的每个数字
for (int num : nums) {
// 对 32 位整数的每一位进行统计
for (int j = 0; j < 32; j++) {
// 将当前位 (num & 1) 加入 counts 中对应的计数
counts[j] += num & 1;
// 右移 num，继续处理下一位
num >>= 1;
}
}
// 初始化结果 res
int res = 0;
// 定义 m 为 3，表示我们将考虑出现次数对 3 取模
int m = 3;
// 处理 counts 数组，将结果构造到 res 中
for (int i = 0; i < 32; i++) {
// 左移 res，为下一位腾出空间
res <<= 1;
// 将 counts 中对应位的出现次数对 3 取模，添加到 res
res |= counts[31 - i] % m;
}
// 返回结果，res 中现在存储的是只出现一次的数字
return res;
}
}
原文地址：https://blog.csdn.net/2403_85375987/article/details/144315649
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！