移位操作符
<<左移 >>后移
移位操作符的操作数只能是整数 ,移动的是的是操作数的二进制数码位置,整数在内存中存放的是补码。
这里移动的的是整数的补码,打印时是原码对的值。
左移操作符:技巧:左边抛弃,右边补零
int main() { int a = 3; int c = a << 1; printf("%d", a);//3 printf("%d", c);//6 int d = -3; int e = d << 1; printf("%d", e);//-6 return 0; }
如图:
右移操作符
右移分两种,1.逻辑移位 左边用零补充,右边丢弃。2.算术移位。左边用该值的符号位填充,右边丢弃
移位采用算术右移还是逻辑右移取决于编译器.
在vs采用的是算术右移
int main() { int a = -5; int b = a >> 1; printf("%d", b);//-3 return 0; }
需要值得注意的是,一个数的二进制位最多时三十二位,移位操作注意其移位大小。
位操作符
位操作符共有三个:& (按位与) |(按位或) ^(按位异或)
对于他们的操作数,也是整数。
int main() { int a = 3; int b = -5; int c = a & b;//按位与 对应二进制位同真为真,有一个为假就是假 1为真,0为假 printf("%d", c);//3 int d = a | b;//按位或 对应的二进制位同假为假,有一个真为真 printf("%d", d);//-5 int e = a ^ b;//按位异或,对应的二进制位相同为假,不同为真 printf("%d", e);//-8 }
如图:
注意的一点是:
0^a = a |
3^3^5 = 5 |
3^5^3 = 5 |
异或是支持交换律的 |
例题
交换两个数,不用第三方变量。
int main() { int a = 3; int b = 5; printf("交换前:a=%d b=%d\n", a, b); a = a ^ b; b = a ^ b; a = a ^ b; printf("交换后:a=%d b=%d\n", a, b); return 0; }
当然这里除了运用按位异或。还可以用
int main() { a = a + b; b = a - b; a = a - b; printf("交换后:a=%d b=%d\n", a, b); }
单身狗问题
给一组数,在这里里面,有两个数字只出现一次,其他数数字都是成对出现的,找出只出现一次的两个数字
1 2 3 4 5 1 2 3 4 6
解题思路:所有的数字异或在一起,因为相同的二进制位异或之后是零,零和一个数异或是他本身。
而这里我们要找两个只出现一次的数,所以这里需要对数进行分组,使得每一组只有一个”单生狗“数,之后再进行异或操作。那麽如何分组呢?
在这里单生狗数是 5和6 ,我们可以发现5与6异或之后的结果是0 1 1,他的二进制位最后一位是1,那我们就按每个数二进制位最后一位是否是1来分组。
1 0 1 - 5
1 1 0 - 6
0 1 1
所以在此之前所有的数异或之后,我们去寻找最后该结果的二进制位哪一位是1,标记该位置。遍历二进制是从后往前的。之后再将每一个数右移至该位置,按位与1判断是否为0,为1则说明该位置的二进制位是0分一组,将该组数异或在一起,为零说明二进制位是1分为一组,将该组数异或在一起,即可以求得该单身狗数。
首先我们要对数进行分组,假设有数组的元素是:1,2,3,4,5,1,2,3,4,6
我们按它的二进制位最后一位是否为1进行分组:
第一组:
最低位是1的数字:1 1 3 3 5
第二组:
最低位是0的数字:2 2 4 4 6
在这里,我们也可以以它的倒数第二位是否为1进行分组
第一组:
倒数第二位是1的数字:6 2 2 3 3
第二组:
倒数第二位是0的数字:1 1 4 4 5
void find_single_dog(int arr[], int sz, int* sd1, int*sd2) { //1. 把所有的数字异或在一起 int ret = 0; int i = 0; for (i = 0; i < sz; i++) { ret ^= arr[i]; } //2. 计算ret的二进制中哪一位是1 int pos = 0; for (i = 0; i < 32; i++)//总共32位二进制位 { if (((ret >> i) & 1) == 1) { pos = i; break; } } //3. 分组异或 for (i = 0; i < sz; i++) { if (((arr[i] >> pos) & 1) == 1) { *sd1 ^= arr[i]; } else { *sd2 ^= arr[i]; } } } int main() { int arr[] = { 1,2,3,4,5,1,2,3,4,6}; int sz = sizeof(arr) / sizeof(arr[0]); int x = 0; int y = 0; find_single_dog(arr, sz, &x, &y); printf("%d %d\n", x, y); return 0; } int main() { char arr[10] = { 0 }; sprintf(arr, "%d", 1234); printf("%s\n", arr);//1234 return 0; }