# 2019 小土刀再启程

0%

## 更新历史

• 2019.08.05：编入新系列
• 2016.01.23：完成初稿

## 简单介绍

~ 位求反 ~var
<< 左移(乘法) var << position
>> 右移(除法) var >> position
& 位与 var1 & var2
^ 位异或 var1 ^ var2

## 解题策略

### 移位操作

1. 将x最右边的n位清零 `x & (~0 << n)`
2. 获取x的第n位值(0或者1) `x & (1 << n)`
3. 获取x的第n位的幂值 `(x >> n) & 1`
4. 仅将第n位置为1 `x | (1 << n)`
5. 仅将第n位置为0 `x & (~(1 << n))`
6. 将x最高位至第n位(含)清零 `x & ((1 << n) - 1)`
7. 将第n位至第0位(含)清零 `x & (~((1 << (n + 1)) - 1))`
8. 仅更新第n位，写入值为v; v为1则更新为1，否则为0 `mask = ~(1 << n); x = (x & mask) | (v << i)`

• Two’s Complement - 负数可以看作是最高位的 1 为负，其他位为正，相加得到最后的值
• 例如 -1 = (1111) 最高位的 1 表示 -8， 剩下三位等于 7，相加后等于 -1
• logical right shift - put a `0` in the most significant bit - `>>>`
• arithmetic right shift - put a `1` in the most significant bit - `>>`

### Get Bit

Shifts 1 over by `i` bits, creating a value that looks like `00010000`. AND operation

### Set Bit

Shifts 1 over by `i` bits, creating a value like `00010000`. OR operation

### Clear Bit

Create a number like `11101111` by creating the reverse of it (`00010000`). AND operation.

To clear all bits from the most significant bit through `i` (inclusive), we create a mask with a `1` at the ith bit(1 << i). Then we subtract 1 from it, giving us a sequence of 0s followed by i 1s. AND operation.

To clear bits from i through 0 (inclusive), we take a sequence of 1s (which is -1) and shift it over by 31 - i bits.

### Update Bit

Set the ith bit to a value `v`