位运算初探

位运算基础

与(&)操作

这里左右是指数字转换成 二进制后的左右, 例如 3 & 5

3 & 5
  011 // 3 的二进制 

& 101 // 5 的二进制

  001 // 结果为 1

如果参加 & 运算的是附属(如 -3 & -5)，则要以补码形式表示为二进制数，然后再按位进行“与”运算

补码就是取反然后加 1

6   二进制    110
    取反   ...001
    加1    ...002
    二进制2要进位 ...010 

• 清零 将二进制数 11100101 的第二位清零 这里的第二位我们是右至左，右边第一个数是 0 位，类似于数组索引

      1110 0101
  &   1111 1011
  -------------
      1110 0001
  

• 取一个数的某些指定位

      1111 1010 取后四位
  &   0000 1111
  -------------
      0000 1010
  

或(|)操作

    0011 0000
|   0000 1111
-------------
    0011 1111

• 使用位运算将小写字母转换成大写字母，大写字母转小写字母

• 小写字母转大写字母

  首先我们可以看出大写字母和小写字母 低四位相同，只要第 5 位为 1 就是大写字母，我们考虑 或(|)操作，根据或(|)操作的特性那我们要找的那个数的低四位应该都是 0。

  我们再看高四位

    高四位
  A 0100
  a 0110
  

  到这我们可以看出，或(|)操作，当位为 1 时此位是无法更改的，所以或(|)操作不可取。

  与(&)操作依旧低四位相同，根据与(&)操作的特性那我们要找的那个数的低四位应该都是 1

    高四位
  A 0100
  a 0110
  ------
    010?
    
  Z 0101
  z 0111
  ------
    0101
  

  由此我们得出我们要找那个数二进制就是 0101 1111，十进制 95

// C语言
printf("%c", 'z' & 95);
// js 
// 'a'.toLocaleUpperCase(); // 字符转大写方法...
String.fromCharCode(("a".charCodeAt() & 95)); // 好麻烦... 

• 大写字母转小写字母

// C语言
printf("%c", 'Z' | 32);
// js
String.fromCharCode(("A".charCodeAt() | 32));  

异或(^)操作

    0011 1001
^   0010 1010
-------------
    0001 0011

• 使特定位反转

设有 0111 1010， 想使其低四位反转，即 1 变 0, 0 变为 1。

    0111 1010
^   0000 1111
-------------
    0111 0101

• 交换两个值，不用临时变量

a ^= b;
b ^= a;
a ^= b;

a = 1 二进制 0001
b = 2 二进制 0010

a ^= b;
  0001
^ 0010
------
  0011
  
b ^= a;
  0011
^ 0010
------
  0001
  
a ^= b;
  0011
^ 0001
------
  0010

左移(<<)和右移(>>)

• x & (1 << n) 就是 取出整数 x 的第 n 位，如果结果大于 0，则该位为 1，反之则为 0

• x | (1 << n) 就是将 x 的第 n 位赋值为 1，

5 | 1 = 7
5 | (1 << 1) = 7
    0101
|   0010
--------
    0111

计算两正整数之和

• 不使用 + 、 -

    0001
+   0101
--------
    0110

• 取出两个数字的相同位，如果都为 1 进位，单个为 1 赋值为 1，否则为 0

• 取位

let bitA = a & flag;
let bitB = a & flag;

• 赋值

let carry = false;// 是否进位
if (bitA && bitB) { // 都为 1
     // 进位
     if (carry) { // 低位已进位(此位 3 个 1)赋值
        let sum |= flag;
     }
     carry = true;
} else if (bitA || bitB) { // 单个为 1
    if (!carry) { // 低位未进位赋值
       // 赋值
       let sum |= flag;
    }
    // 如果低位已进位(此位 2 个 1)进位
} else { // 都为 0
    if (carry) { // 低位已进位赋值
        let sum |= flag;
        carry = false;
    }
}

const getSum = function (a, b) {
    let sum = 0;
    let flag = 1;
    let carry = false;
    while (flag <= a || flag <= b) {
        let bitA = a & flag;
        let bitB = b & flag;
        if (bitA && bitB) {
          if (carry) {
            sum |= flag;
          }
          carry = true;
        } else if (bitA || bitB) {
          if (carry) {
            carry = true;
          } else {
            sum |= flag;
          }
        } else {
          if (carry) {
            sum |= flag;
          }
          carry = false;
        }
        flag <<= 1;
    }
    if (carry) {
        sum |= flag;
    }
    return sum;
};