> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/topics/bit-manipulation.md).

# Bit Manipulation

bit manipulation

## Basic Operations

```
左移操作 A << B
右移操作 A >> B, A >>> B
按位与操作 A & B
按位或操作 A | B
按位非操作 ~A
异或操作 A ^ B, 异或操作也就是不进位加法，比如1 + 1 = 10， 我们只取个位，不要进位的那个1，其他同理。

two's complement: -x = ~x + 1
```

## Tricks

<http://www.jiuzhang.com/tutorial/bit-manipulation/84>

* `n & (n-1)` remove last `1` in binary

<https://leetcode.com/problems/power-of-two/description/> <https://leetcode.com/problems/number-of-1-bits/description/>

* determine odd/even: `n % 2` or `n & 1`, `n & 1` is better, unsigned integer can be larger than Integer.MAX\_VALUE
* get last bit: `x & -x`

### `+, -, *, /` operations

```java
// Iterative
public int getSum(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;

    while (b != 0) {
        int carry = a & b;
        a = a ^ b;
        b = carry << 1;
    }

    return a;
}

// Iterative
public int getSubtract(int a, int b) {
    while (b != 0) {
        int borrow = (~a) & b;
        a = a ^ b;
        b = borrow << 1;
    }

    return a;
}

// Recursive
public int getSum(int a, int b) {
    return (b == 0) ? a : getSum(a ^ b, (a & b) << 1);
}

// Recursive
public int getSubtract(int a, int b) {
    return (b == 0) ? a : getSubtract(a ^ b, (~a & b) << 1);
}

// Get negative number
public int negate(int x) {
    return ~x + 1;
}
```