Leetcode C++位运算（整型 字符型）详解及其应用 判断奇偶、符号变换、绝对值、相反数、数据交换、高低位互换、幂次判断_字符串重复的位运算原理

位运算使用的数据类型是整型和字符型
注意单个字符也能进行异或运算 本质也是ASCII二进制码的异或
异或结果的最终解释要看结果变量的类型
不仅整型之间、字符型可以异或 整型和字符串型之间也可以异或

一、原码 反码 补码

正数的原码，反码，补码，移码都等于原码
负数的反码=原码取反 (符号不变)
负数的补码=反码+1
负数的移码=补码的符号位取反

二、位运算原理

对转换成二进制的数字进行每一位上的0、1的运算，：
与(&)，或(|)，异或(^)，左移(<<)，右移(>>)

在计算机组成原理中移位运算如下（无符号数左右逻辑移都是补充0）

但是计算机中都是用补码进行运算的 有符号数（算术移位）：
正数 不管左移右移都是补0（左移末尾补0 右移高位补和符号位 即0）
负数 左0右1（左移末尾补0 右移高位补和符号位 即1）
按照移动规则括号里面的叙述 那么有符号数不管正数负数的移动规则都是一样的 左移末尾补0 右移高位补和符号位 因此在写代码时并不影响代码的实现

m>>n m 右移n位
m<<n m 左移n位
有符号数移位运算等价于2的幂次乘除法运算

无符号数：左移右移都是补0（逻辑移位）

如在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，若要求将一个无符号数的二进制位反转后输出，输入和输出都将被指定为有符号整数类型，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的，只是最后编译器会根据声明的变量是有股好还是无符号去解释数据为十进制输出给人看，十进制的结果的解释最终是由于编译器去做这件事的，见leetcode例题无符号数的二进制位反转后输出的几种方法

位运算的规律：
1.进行位运算时都是用数据的补码进行运算。
2.运算后得到的结果也是补码，需要将它转换成原码才能得到结果。

其实不光位运算计算机中所有运算都遵循补码运算 结果为负要减1求反这个规则
如果运算后得到的二进制串是一个正数（最高位为0）可以不转因为正数的补码和原码相同；如果为负数 减1再求反

#include <iostream>
void main()
{
 	//-----------正数按位运算-----------
	//按位右移  >> 往右移一位 
	//0000 0000 0000 1010
	//0 0000 0000 0000 101
	short sValue1 = 10 >> 1;
	printf("sValue1=%d\n", sValue1);  //5
 
	//按位左移  << 往左移一位 
	//0000 0000 0000 1010
	//000 0000 0000 1010 0
	short sValue2 = 10 << 1;
	printf("sValue2=%d\n", sValue2); //20

	//按位或 |
	//0000 0000 0000 1111
	//0000 0000 0000 1010
	//0000 0000 0000 1111
	short sValue3 = 15 | 10;
	printf("sValue3=%d\n", sValue3);//15
	
	//按位与 & 
	//0000 0000 0000 1111
	//0000 0000 0000 1010
	//0000 0000 0000 1010
	short sValue4 = 15 & 10;
	printf("sValue4=%d\n", sValue4); //10
	
	//按位异或  ^ 
	//0000 0000 0000 1111
	//0000 0000 0000 1010
	//0000 0000 0000 0101
	short sValue5 = 15 ^ 10;
	printf("sValue5=%d\n", sValue5);//5
	
	//按位非 ~  
	//0000 0000 0000 1010          
	//1111 1111 1111 0101（结果为负数 且是计算机中是补码表示）
	//需要补码转原码
	//->1111 1111 1111 0100(减1得反码)->1000 0000 0000 1011(求反得原码)
	short sValue6 = ~10;
	printf("sValue6=%d\n", sValue6);//11
 
    
 
	//-----------负数安位运算-----------//
	//负数用补码来运算
 
	//按位或  |  
	//1000 0000 0000 1111（-15原码）
	//->1111 1111 1111 0000（反码）
	//->1111 1111 1111 0001(补码)
	
	//1111 1111 1111 0001
	//0000 0000 0000 1010          
	//1111 1111 1111 1011（补码）
	//结果为负的补码 减1求再求反
	//->1111 1111 1111 1010（反码）->1000 0000 0000 0101(原码)
	short sValue7 = -15 | 10;
	printf("sValue7=%d\n", sValue7);//-5
 
	//按位与 &
	//1000 0000 0000 1111（-15原码）
	//->1111 1111 1111 0000（反码）
	//->1111 1111 1111 0001(补码)
	
	//1111 1111 1111 0001
	//0000 0000 0001 0100
	//0000 0000 0001 0000（补码）
	//结果为正的补码 不用再转
	short sValue8 = -15 & 20;
	printf("sValue8=%d\n", sValue8);//16

	//按位非 ~           
	//1111 1111 1111 0001
	//0000 0000 0000 1110  (正的补码)
	short sValue10 = ~-15;
	printf("sValue10=%d\n", sValue10);//14
 
	//按位右移  >> 往右移一位  最高位补上和符号位相同的数 即1
	//1000 0000 0000 1010  （原码）
	//->1111 1111 1111 0101（反码）
	//->1111 1111 1111 0110（补码） 
	
	//1111 1111 1111 0110
	//1 1111 1111 1111 011（结果为负的补码 减1再求反）
	//->1111 1111 1111 1010 （反码）
	//->  1000 0000 0000 0101 （原码）
	short sValue11 = -10 >> 1;
	printf("sValue11=%d\n", sValue11);// -5
	
	//按位左移  << 往左移一位  最末位补0
	//1111 1111 1111 0110 （补码）
	//111 1111 1111 0110 0 （结果为负的补码 减1再求反补码）
	//->1111 1111 1110 1011 （反码）
	//->1000 0000 0001 0100（原码）
	short sValue12 = -10 << 1;
	printf("sValue12=%d\n", sValue12);//-20
	system("pause");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

三、位运算的巧妙运用

与 &的应用
1 、清零：A&0（也可指定清零某些位）
2 、取指定位　
3 、 判断奇偶性 ：只根据最末位是0还是1判断整数的奇偶性如整数n

if((n & 1) == 0）来判断 比用 if(n%2==0) 判断奇偶性效率高。
将int型变量a的第k位清0，即a=a&~(1<<k)
将int型变量a的第k位置1，即a=a|(1<<k)
1
2
3

异或^ 的应用
1、特定位翻转 要使哪几位翻转就将其和相应位为1的数进行∧运算
2、数据交换，交换两个值不用临时变量.

void swap(int &a, int &b)
{
    if (a != b){
        a ^= b;//a=(a^b);
        b ^= a;//^运算满足交换律，b=b^(a^b)=b^b^a=a
        a ^= b;//a=a^b=(a^b)^a=a^a^b=b
    }
}
1
2
3
4
5
6
7
8

3、变换符号 ：x 的 相反数为 (~x+1)
正负号变换只需将原数的二进制取反后加1

short a = 11;  //a的补码0000 1011
short b=~a     //b的补码 1111 0100 位运算的结果为负的补码
				// 减1->1111 0011（反码）
                //求反->1000 1100（原码）-12
                
short c=b+1;   //c的补码 1111 0101 结果为负的补码 
               //  减1->1111 0100
               // 求反->1000 1011（原码）-11
 //其实求c的时候已经是short型数据的四则运算 但是计算机中仍然是以补码加法来算的
printf("%d\n", c)//a c 符号相反

short d = -11;  //d的原码1000 1011 补码1111 0101
short e=~d     //e的补码 0000 1010 即10
short f=e+1;   //f的补码 0000 1011 即11
printf("%d\n", f)//d f 符号相反
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

同时求反再加一还有一个妙用 ：仅保留二进制串里面最右边的那一个1: (x & -x)
检测室2的幂次: (x & -x)==x
去除最右边的1检测2 的幂次：（x & (x-1)）== 0

4、求绝对值（与负数交换符号原理相同）

int abs( int x )
{
    int y ;
    y = x >> 31 ;
    return (x^y)-y ;        //or: (x+y)^y
    y就是x的符号位 
    假如x为正 y=0（32个0 正数移位是补0 解释出来仍是十进制0）(x^y)-y=x-0=x 
    假如x为负 y=-1
    (这里是指十进制-1 在机器中取出来的符号位那一位仍然是1 y的二进制是32个1)
    (为负数时在计算机中是补码右移补1 结果为负要转成原码 32个1转成原码十进制是-1)
 
    (x^y)即二进制串与全1求异或 相当于对二进制按位求反再减-1即
    求反再加1 (x^y)-y就等于求反再加1  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

5、高低位互换
16位的无符号整数。称这个二进制数的前8位为“高位”，后8位为“低位”。例如，数34520用二进制表示为：10000110 11011000
将它的高低位进行交换，我们得到了一个新的二进制数：11011000 10000110它即是十进制的55430。

设x=34520=10000110 11011000 由于x为无符号数，右移时会执行逻辑右移即高位补0，因此x右移8位将得到00000000 10000110。而x左移8位将得到11011000 00000000。可以发现只要将x>>8与x<<8这两个数相或 就可以得到1101100010000110。
基于这个原理可以采用分治对对任意二进制串逆序，只是这种方法需要自己去手动计算哪些位做与运算（实际上就是每次互换的那些位取1 其他位取0） 不过不用任何循环完全只用位运算就可以实现*

我们可以通过以下步骤实现32 位翻转：
首先，我们将原来的 32 位分为 2 个 16 位的块。
然后我们将 16 位块分成 2 个 8 位的块。
然后我们继续将这些块分成更小的块，直到达到 1 位的块。
在上述每个步骤中，我们将中间结果合并为一个整数，作为下一步的输入。

    uint32_t reverseBits(uint32_t n) {
        高16位和第16位互换后的n
        n = (n >> 16) | (n << 16);
        
        现在将2个16位的块中各自的高8位0xff00和低8位0x00ff互换后合并
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
        
        现在将4个8位的块中各自的高4位0xf0和低4位0x0f互换后合并
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
        
        现在将8个4位的块中各自的高2位1100 即0xc和低2位0011即0xc互换后合并
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
        
        现在将16个2位的块中各自的高1位10 和低1位01互换后合并
        相邻两个2位的块组成一个4位的块 即1010=0xa 或者0101=0x05
        共8个4位的块
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
        return n;
        
如16位10000110 11011000 高8位和低8位互换后
->11011000 10000110
->(11011000 10000110 & 11110000 11110000)>>4|取各自的高四位 并左移
  (11011000 10000110 & 00001111 00001111)<<4 取各自的低四位 并右移
->11010000 10000000>>4 |00001000 00000110<<4
->00001101 00001000 | 10000000 01100000
->10001101 01101000   
  与 11011000 10000110 相比各自的8位中高四位和低四位已经互换
  难点就是自己要去算与的那个数是哪些位取1实际上就是每次互换的那些位取1 其他位取0
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

6、判断一个整数是不是2的整数次方
如果一个整数是2的整数次方，那么它的二进制标识中一定有且只有一位是1，而其他所有位均为0. 解决方案：
把这个整数减去1之后再和本身做与运算，这个整数中唯一的一个1就会变成0.所以只要判断是不是等于0即可。

位运算的优先级超级超级超级低 尽量都打括号

    bool isPowerOfTwo(int n) {
          
         if(n==INT_MIN||n<0) return false;
         if(( n & (n-1))==0 && (n!=0)) return true;
         else return false;
         
不能是 n & (n-1)==0 会先赋值 

计算机中是补码表示负数，负数时可能会溢出int型范围 [-2^31,2^31-1] n=-2^31时n-1就溢出因此需要判断n==INT_MIN 又有任何数的幂次都大于0 但0和任何数与都等于0 因此可直接n<=0时false
  

    }
1
2
3
4
5
6
7
8
9
10
11
12
13

7、循环移位

将int型变量循环左移k次，即a=a<<k|a>>16-k   (设sizeof(int)=16)
将int型变量a循环右移k次，即a=a>>k|a<<16-k  (设sizeof(int)=16)
1
2

8、2幂次的取模运算转化成位运算 (在不产生溢出的情况下)

   a % (2^n) 等价于 a & (2^n - 1)
   
   也就是求对应位后面为1的那些
   如42%8 = 2 =42 & 7
   0010 1010 & ( 0000 1000 -1) =
   0010 1010 & 0000 0111 =
   0000 0010
   -42%8= 6 =-42 & 7 注意余数一定是正数
   1010 1010（-42的原码） 求反加1 ->1101 0110（-42的补码）
   1101 0110 & 0000 0111=0000 0110 =6
1
2
3
4
5
6
7
8
9
10

求输入是一个无符号整数的二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
每次把最后一个一翻转 计数加一 直到n变成0

public int hammingWeight(int n) {
    int sum = 0;
    while (n != 0) {// 并不是去扫描n的每一位
        sum++;
        n &= (n - 1);
    }
    return sum;
}
1
2
3
4
5
6
7
8