# 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;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jaywin.gitbook.io/leetcode/topics/bit-manipulation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.