这里主要是在位运算介绍二的基础上再结合实例对位运算进行介绍。
#####实例一##### 我们通常使用的移位操作都是算术移位。那么如果要实现循环移位该如何做呢？
1、循环右移
int size = 8;
unsigned char a = 0xAD; //二进制表示为 1010 1101
a = (a >> 2) | (a << (size - 2)); //a为 0110 1011
printf("%.2x\n", a);
/*对于一个 n bits 的数。循环右移 R 位，可以通过将数算术右移 R 位，然后
将数的低 R 位左移 n - R 位。并将其与算术右移的结果作或运算。*/
2、循环左移
int size = 8;
unsigned char a = 0xAD; //二进制表示为 1010 1101
a = (a << 2) | (a >> (size - 2)); //a为 1011 0110
printf("%.2x\n", a);
/*对于一个 n bits 的数。循环左移 L 位，可以通过将数算术左移 L 位，然后
将数的高 L 位右移 n - L 位。并将其与算术左移的结果作或运算。*/
#####实例二##### 1、n 个数中，有一个数只出现一次，其他数都出现两次。求这个只出现一次的数。(出现一个可以换成出现奇数次，出现两次可以换成出现偶数次)。
int unique = 0;
int arr[5] = {1, 1, 2, 3, 2};
for (int e = 0; e < 5; e++) {
unique ^= arr[e];
}
//将数组中所有的数异或一次，得到的结果即为那个只出现一次的数。
2、n个数中，有两个数各出现一次，其他数都出现两次。求出这两个只出现一次的数。
int x = 0, y = 0, xy = 0;
int arr[6] = {1, 1, 2, 3, 2, -2};
for (int e = 0; e < 6; e++) {
xy ^= arr[e];
}
//xy 中存储的是那两个只出现一次的数相异或的结果
int b = xy & -xy;
//选取 xy 中任意一个为 1 的位。方便起见就取最低位。
for (int e = 0; e < 6; e++) {
if(b & arr[e]) {
x ^= arr[e];
} else {
y ^= arr[e];
}
}
/*假设选取 xy 中为 1 的位为第 k 位。因为 xy 为数组中只出现
一次的两个数相异或的结果。所以这两个数中肯定有一个数第
k 位为 1 。而另一个数的第 k 位为 0 。且由于这两个数不等。
xy 中肯定有为 1 的位。然后将数组中的数分为两类。第 k
位为 1 的分为一类。第 k 位为 0 的分为一类。这样再按照前
面异或的方法可以求出这两个数。*/
printf("%d %d\n",x, y);
#####实例三##### 将一个数的二进制形式倒序。如0011 0011倒序为 1100 1100
方法一
int size = 8;
unsigned char a = 0x33, low, rev = 0;
while (a) {
//取 a 中为 1 的最低位
low = a & -a;
//设置倒序时该位的位置
rev |= (1 <<(size - 1)) / low;
//将 a 中为 1 的最低位变为 0
a = a ^ low;
}
//循环的执行次数为a中1出现的次数。但有除法，会影响效率
printf("%.2x\n", rev);
方法二
//再次利用分治思想。分治在这里真是万能神器
int a = 0x33333333;
a = ((a & 0x55555555) << 1) | ((a & 0xAAAAAAAA) >> 1);
a = ((a & 0x33333333) << 2) | ((a & 0xCCCCCCCC) >> 2);
a = ((a & 0x0F0F0F0F) << 4) | ((a & 0xF0F0F0F0) >> 4);
a = ((a & 0x00FF00FF) << 8) | ((a & 0xFF00FF00) >> 8);
a = ((a & 0x0000FFFF) <<16) | ((a & 0xFFFF0000) >>16);
//第一句的意思是交换 a 中奇数位和偶数位的值
//第二句的意思是指从第 0 位起，每 4 位中交换高 2 位和低 2 位
//最后一句是交换高 16 位和低 16 位的二进制内容
printf("%x\n", a);
//但这种方法也有限制就是扩展性不强。二进制位数不同，写法
//也不同，如以上写法是针对 32 位的整数而言。
#####实例四##### 给定一个数a，求下一个大于或者等于a且是2的幂的数。例如15,大于或等于它且为2的方幂的数为16。
方法一
/*利用二分法，求的数中为 1 的最高位。然后判断
数是否是 2 的方幂。如果是直接输出，否则取数
的最高位，并再左移一位即为所求。*/
int a = 0x00003FF0, n = 0, p = 16, b = a;
while (p) {
if ((a >> p) > 0) {
n += p;
a >>= p;
}
p >>= 1;
}
/*循环的意思是首先判断为 1 的最高位是否在高 16 位。
然后判断是否在高 8 位。如此循环。直到计算出最
高位的位置。*/
if ((b & b - 1) == 0) {
printf("%x\n", b);
} else {
printf("%x\n", 1 << (n + 1));
}
/*if 语句首先判断该数是否本身是 2 的方幂，如果是
直接输出。否则将最高位左移一位。作为结果输出。*/
方法二
/*设一个数为 1 的最高位为第 k 位。利用分治的思想。将该数的
第 k 位到第 0 位全部设为 1 。然后将该数加 1 。即为所求。*/
int a = 0x00003FF1;
a--;
a = a | (a >> 1);
a = a | (a >> 2);
a = a | (a >> 4);
a = a | (a >> 8);
a = a | (a >> 16);
a++;
printf("%x\n", a);
/*第一句 a-- ，是为了防止 a 本身就是 a 的方幂。接下来的 5 句就是将
一个 32 位正数的第 k 位到第 0 位全部设置为 1 （假设 a 中为 1 的最高
位为第 k 位）。这里我们只考虑第 k 位。第一句话将 k , k - 1 设置
为 1 ，第二句将 k 到 k - 3 设置为 1 。同理第三句将 k 到 k - 7 设置为 1
如此继续。可以将第 k 位到第 0 位全部设置为 1 。然后 a + + 即为所求。*/
####引用####