位运算

• 与 int&1

// 4 & 1
4 ==> 100
1 ==> 001
& ==> 000 ==> (int)0
.......*
// 3 & 1
3 ==> 11
1 ==> 01
& ==> 01  ==> (int)1
// 128 & 2
128 ==> 10000000
2   ==> 00000010
&   ==> 00000000  ==> (int)0

• “10000” & “1000”

"10000" & "01000" ==> "00000"

• 或 (计算优先级低)

"10000" | "01000" ==> "11000"

• 右移 »

26 >> 2 ==> "11010" >> 2 ==> 110 ==> (int)6

• 左移 «

26 << 2 ==> "11010" << 2 ==> 1101000 ==> (int)104

• 取反 ~ (计算优先级高)

负数是用补码表示的，补码是原码取反+1

~26 ==> -27
26  ==> 0.....0 11010 // 32位或64位
~26 ==> 1.....1 00101 // 32位或64位 补码
........*             // 补码 第一位0正1符        -
        1.....1 00100 // 原码取反
        0.....0 11011 // 原码 bindec("11011") ==> 27

~26 ==>                                          -27

• 异或 ^

一个为 1 另一个为 0 的位设为 1

26^27

26 ==> 11010            128 ==> 10000000
27 ==> 11011            127 ==> 01111111

^  ==> 00001            ^   ==> 11111111
       (int)1                   (int)255

• 位运算分治

leetcode 190.颠倒给定的32位无符号整数的二进制位

    $m1 = 0x55555555 // 01010101010101010101010101010101 // 一个一组
n=26         ==>        00000000000000000000000000011010
    n>>1     ==>        00000000000000000000000000001101
(n>>1) & $m1 ==>        00000000000000000000000000000101     5

    n&$m1    ==>        00000000000000000000000000010000     16
(n&$m1) << 1 ==>        00000000000000000000000000100000     32

step1                   00000000000000000000000000100101  ==> 37

    $m2 = 0x33333333 // 00110011001100110011001100110011 // 两两一组
n=37         ==>        00000000000000000000000000100101
    n>>2     ==>        00000000000000000000000000001001      10
(n>>2) & $m2 ==>        00000000000000000000000000000001      1

    n&$m2    ==>        00000000000000000000000000100001      33
(n&$m2) << 2 ==>        00000000000000000000000010000100      132

step2        ==>        00000000000000000000000010000101      133

    $m4 = 0x0f0f0f0f // 00001111000011110000111100001111 // 四个一组
n=133        ==>        00000000000000000000000010000101
    n>>4     ==>        00000000000000000000000000001000      8
(n>>4) & $m4 ==>        00000000000000000000000000001000      8

    n&$m4    ==>        00000000000000000000000000000101      5
(n&$m4) << 4 ==>        00000000000000000000000001010000      80

step3        ==>        00000000000000000000000001011000      88

    $m8 = 0x00ff00ff // 00000000111111110000000011111111 // 八个一组
n=88        ==>         00000000000000000000000001011000
    n>>8     ==>        00000000000000000000000000000000
(n>>8) & $m8 ==>        00000000000000000000000000000000

    n&$m8    ==>        00000000000000000000000001011000      88
(n&$m8) << 8 ==>        00000000000000000101100000000000

(n >> 8) & $m8 | (n&$m8) << 8
step4        ==>        00000000000000000101100000000000      ==> 22528

             ==>        00000000000000000000000000000000
             ==>        01011000000000000000000000000000

step5        ==>        01011000000000000000000000000000      1476395008
n=26         ==>        00000000000000000000000000011010

原理 1234 5678

1234 5678
1001 0101

step1
1234  01            5678 01
      01                 05
      20                 60
      21                 65

        03                 07
        40                 80
        43                 87

      2143               6587
step2
2143  0011          6587 0011
      0021               0065
      4300               8700
      4321               8765
step3
43218765    00001111
            00004321
            87650000
            87654321

8765 4321

step1具体:

12345678
10010101

12345678 >> 1 ==> 01234567 ==> 01001010 ==> 01001010 & 01010101 ==> 01000000
12345678 ==> 10010101 & 01010101 ==> 00010101 ==> 00010101 << 1 ==> 00101010

    01000000
    00101010
    01101010  // step1实际结果
    --------
    12345678
    10010101
    --------
    21436587
    01101010  // step1预计
    --------