Java教程
专题复习：位运算
注意：位运算& ^等 一定 要加括号 否则会 可能由于运算符优先级的问题导致意想不到的结果
(n&(n-1))可以消除n的二进制中最右边的1
(n&(-n) )可以只保留二进制中最右边的1
剑指 Offer 15. 二进制中1的个数
方法一： 进行移位操作
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
for(int i = 0; i < 32; i++)
{
if(n>>i&1) count++;
}
return count;
}
};
方法二：对方法一进行优化，因为有的n不需要移位32位
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while(n)
{
count += (n&1);
n>>=1;
}
return count;
}
};
方法三：不是n进行移位操作，而是1进行移位操作
class Solution {
public:
int hammingWeight(uint32_t n) {
int res = 0;
while(n)
{
if(n&0x1) res++;
n = n>>1;
}
return res;
}
};
方法四：利用n&n-1 可以消除 n中最右边的1
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while(n)
{
n&=n-1;
count++;
}
return count;
}
};
方法五：查表法
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
int table[16] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
while(n)
{
count += table[n&0xf];
n>>=4;
}
return count;
}
};
方法6：二进制平行算法
class Solution {
public:
int hammingWeight(uint32_t n) {
n = (n&0x55555555)+((n>>1)&0x55555555); //n为32位，相邻两位进行相加
n = (n&0x33333333)+((n>>2)&0x33333333); // 相当于2位为一个单位， 相邻两个单位相加
n = (n&0x0f0f0f0f)+((n>>4)&0x0f0f0f0f); // 相当于4位为一个单位， 相邻两个单位相加
n = (n&0xff00ff)+((n>>8)&0x00ff00ff); // 相当于8位为一个单位， 相邻两个单位相加
n = (n&0xffff)+((n>>16)&0xffff); //相当于16位为一个单位， 相邻两个单位相加
return n;
}
};
leetcode231. 判断一个数是否为2 的幂
思路：一个数 如果是2的幂，那么该数的二进制中质保函1个1.
方法一： 利用移位来计算n中1的个数
class Solution {
int count1Num(int n) //计算n 若用二进制表示时 其中1的个数
{
int count = 0;
while(n)
{
count += (n&1);
n>>=1;
}
return count;
}
public:
bool isPowerOfTwo(int n) {
return n > 0 && count1Num(n) == 1;
}
};
方法二：利用n&(n-1)可以去掉 n中最右边的1
这种方法超级简单
class Solution {
public:
bool isPowerOfTwo(int n) {
return n > 0 && (n&(n-1))==0;
}
};
剑指 Offer 56 - II. 数组中数字出现的次数 II
其中一个数只出现一次，另外的数都出现三次，找到这个出现一次的数。
统计数组中，所有元素在 32位中每一位 1出现的次数，如果某一位上1出现的次数 count1Num%3 ==1，说明 该位上的1属于那个只出现一次的数。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for(int i = 0; i < 32; i++)
{
int count1Num = 0;
for(int j = 0; j < nums.size(); j++)
{
count1Num += (nums[j] >> i)&1;
}
if(count1Num % 3 != 0)
{
res |= (1<<i);
}
}
return res;
}
};
对于数组中，如果只有一个数字出现一次，其他数字都出现奇数次n（n > 1），我们可以用下面代码来找到只出现一次的数字。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for(int i = 0; i < 32; i++)
{
int count1Num = 0;
for(int j = 0; j < nums.size(); j++)
{
count1Num += (nums[j] >> i)&1;
}
if(count1Num % n != 0)
{
res |= (1<<i);
}
}
return res;
}
};
对于数组，如果只有一个数字出现一次，其他数字都出现偶数次，我们只需要把所有数字异或一
遍即可找到出现一次的数字。
对应leetcode136. 只出现一次的数字
class Solution {
public:
int singleNumber(vector<int>& nums) {
int size = nums.size();
if(size == 0) return 0;
int res = 0;
for(int i = 0; i < size; i++)
{
res ^= nums[i];
}
return res;
}
};
leetcode 1442. 形成两个异或相等数组的三元组数目
思路：让 a = b 即 a ^ b = 0 即：
我 们 只 需 要 从 数 组 arr 中 找 到 一 些 连续的 元 素 ， 他 们 的 异 或 结 果 等
于0即可。
class Solution {
public:
int countTriplets(vector<int>& arr) {
int count = 0;
int size = arr.size();
for(int i = 0; i < size - 1; i++)
{
int temp = arr[i];//注意 起始值为arr[i]
for(int k = i + 1; k < size; k++)
{
temp ^= arr[k];
if(temp == 0)
{
count += k - i;
}
}
}
return count;
}
};
剑指 Offer 53 - II. 0～n-1中缺失的数字
方法一：利用位运算 nums[i] &i
class Solution {
public:
int missingNumber(vector<int>& nums) {
int size = nums.size();
int res = 0;
for(int i = 0; i < size; i++)
{
res ^= nums[i]^i;
}
return res^size;
}
};
方法二：暴力遍历
class Solution {
public:
int missingNumber(vector<int>& nums) {
for(int i = 0; i < nums.size(); i++)
{
if(nums[i]!=i) return i;
}
return nums.size();
}
};
方法三：利用二分法
class Solution {
public:
int missingNumber(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while(left <= right)
{
int med = (left + right)/2;
if(nums[med] == med) left = med + 1;
else right = med - 1;
}
return left;
}
};
leetcode461:https://leetcode-cn.com/problems/hamming-distance/ 汉明距离
class Solution {
public:
int hammingDistance(int x, int y) {
int temp = x^y;//在求temp对应的二进制中1的个数
int res = 0;
while(temp)
{
if(temp & 1 == 1) res++;
temp >>= 1;
}
return res;
}
};
剑指 Offer 56 - I. 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int size = nums.size();
int temp = 0;
for(int i = 0; i < size; i++)
{
temp ^= nums[i];
}
temp &= -temp;
int res1 = 0, res2 = 0;
for(int j = 0; j < size; j++)
{
if((temp & nums[j]) == 0)//(temp & nums[j])注意要加括号
{
res1 ^= nums[j];
}
else
{
res2 ^= nums[j];
}
}
return {res1, res2};
}
};
位运算求最小的2的n次方
方法一：
int lowPower(int n)
{
int temp = 1;
while(n > temp)
{
temp <<= 1;
}
return temp;
}
方法二：利用位运算
举例：
所 以 一 种 最 简 单 的 方 式 就 是 通 过 移 位 运 算 ， 把 53 最 左 边 的 1 全 部 往 右 边 铺 开 ， 就 变 成 了00111111，然后再加1就变成了了01000000。
但 是 这 里 有 个 小 问 题 就 是 ， 如 果 x 本 来 就 是 2 的 n 次 方 ， 比 如 x 是 16 ， 运 算 的 结 果 就 会 变成 32 ， 而我 们 实 际 要 求 的结果应该是16 。 所 以 这 里 我 们 可 以 先 让 x-1 ， 然 后 再 进 行 运 算。
int lowPower(int n)
{
n = n - 1;
//将最高位1之后的都变为1
n |= (n>>1);
n |= (n>>2);
n |= (n>>4);
n |= (n>>8);
n |= (n>>16);
return n+1;
}
不使用“+”,“-”实现四则运算
(1) 加法 leetcode371：https://leetcode-cn.com/problems/sum-of-two-integers/
a = 3 011
b = 5 101 a&b = 001 a&b<<1 表示有进位 a^b = 110 表示除了进位剩下的 位的数
（a&b<<1） + (a^b) = a + b = 8 又不能使用+ ，因此可以利用递归实现。
方法一：递归的写法存在问题：
如果是负数 leetcode左移时报错 runtime error: left shift of negative value
具体原因是运行时库的问题？
可以转换成无符号整型进行左移
注意：为了解决上述问题，要负数转化为unsigned int类型，因此 ((unsigned int)a&b)<<1
class Solution {
public:
int getSum(int a, int b) {
if(a == 0 ||b == 0)
return a^b;
return getSum(a^b, ((unsigned int)a&b)<<1);
}
};
方法二：
class Solution {
public:
int getSum(int a, int b) {
while(b)
{
unsigned int temp = ((unsigned int)(a&b))<<1;
a ^= b;
b = temp;
}
return a;
}
};
（2）不用 “--”号 实现减法
方法一：利用递归
//实现 a - b
int substract(int a, int b)
{
if(b == 0) return a;
int c = a&b; //找到a和b 相同位的1
a ^= c; //去除a中 与b相同的部分
b ^= c; //去除b中 与a相同的部分
substract(a|b, b<<1);
}
方法二：
//实现 a - b
int substract(int a, int b)
{
while(b)
{
int temp = a^b;
a ^= temp;
b ^= temp;
a |= b;
b <<= 1;
}
return a;
}
leetcode 693. 交替位二进制数 https://leetcode-cn.com/problems/binary-number-with-alternating-bits/
注意：加上long 是为了避免当 n为2^31 -1时， n+1会越界
class Solution {
public:
bool hasAlternatingBits(int n) {
n ^= (n>>1);
return (n&((long)n+1)) == 0;
}
};
-
大厂数据结构与算法教程：入门级详解12-26
-
大厂算法与数据结构教程：新手入门指南12-26
-
Python编程入门指南12-26
-
数据结构高级教程：新手入门及初级提升指南12-26
-
并查集入门教程：从零开始学会并查集12-26
-
大厂数据结构与算法入门指南12-26
-
大厂算法与数据结构入门教程12-26
-
二叉树入门教程：轻松掌握基础概念与操作12-26
-
初学者指南：轻松掌握链表12-26
-
平衡树入门教程：轻松理解与应用12-26
-
数据结构入门教程：轻松掌握基本概念与应用12-26
-
数据结构与算法入门指南12-26
-
算法面试攻略：从零开始的入门指南12-26
-
Python编程基础：变量与类型12-26
-
算法与数据结构高级：新手入门教程12-26
