# [leetcode] bit manipulation

## Introduction

Two’s Complement

8-bit integer, Use first slot to represent the sign of the number. `0` => `+`, `1` => `-`

Shifting

Logical & Arithmatic

Parity Check
Parity checks are used to detect single bit errors in data storage and communication. The parity of a binary value is 1 if the number of 1s in the value is odd; otherwise it’s 0.

General Tricks

### 191. Number of 1 Bits

[Solution]
Use a mask from `000...01` to `1000...0` to test if any of the slots is 1

### Find a closest integer with the same weight

Define the weight of a nonnegative integer x to be the number of bits that are set to 1.

[Solution]
Suppose we flip the bit at index k1 and flip the bit at index k2, k1 > k2. Then the absolute value of the difference between the original integer and the new one is 2^k1 - 2^k2. Since we must preserve the weight, we should make k1 as small as possible and k2 as close to k1.

In summary, the correct approach is to swap the two rightmost consecutive bits that differ.

### 43. Multiply Strings

[Solution] Iterate through x, adding 2^k*y to the result if the kth bit of x is 1. 2^k*y can be computed by left-shifting y by k.

### 29. Divide Two Integers

[Solution]

• Starting from k = 32, if 2^k y < x: x = x - 2^k y, res += 2^k
• O(N^2)

### 136. Single Number

[Solution]

• `0 ^ any = any`
• `any ^ any = 0`

### 67. Add Binary

Solution: The key is the `carry`.

### 1073. Adding Two Negabinary Numbers

Solution:
The `carry` can have three status: `-1`, `0`, and `1`.

### 1017. Convert to Base -2

Solution: Convert to base 2 first, and then add `-`