# Bit Manipulation

> <https://discuss.leetcode.com/topic/50315/a-summary-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently>

* 这个帖子讲得非常好！

## 基本操作总结

* Set union `A | B`
* Set intersection `A & B`
* Set subtraction `A & ~B`
* Set negation `ALL_BITS ^ A` or `~A`
* Set bit `A |= 1 << bit`
* Clear bit `A &= ~(1 << bit)`
* Test bit `(A & 1 << bit) != 0`
* Extract last bit `A &-A` or `A & ~(A - 1)` or `x ^ (x & (x-1))`
* Remove last bit `A & (A-1)`
* Get all 1-bits `~0`

## XOR (^) tricks

* XOR 主要用来剔除掉**偶数个的相同元素**，而生下来单独存在的元素
* 特性：&#x20;

(1) 恒等律：`A ^ 0 = A`

(2) 归零律: `A ^ A = 0`

相同的元素互相抵消；任何元素与 0 异或得到本身。

### eg1: 不使用其他空间，交换两个值

```
a = a ^ b;    
b = a ^ b;   // b = a ^ b = a ^ b ^ b = a ^ 0 = a
a = a ^ b;   // a = a ^ a ^ b = b
```

### eg2: Missing Number

> Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array. For example, Given nums = \[0, 1, 3] return 2. (Of course, you can do this by math.)

```java
public class Solution {
    public int missingNumber(int[] nums) {
        int index = 0, xor = 0;
        for (int i = 0; i < nums.length; i++) {
            xor ^= index ^ nums[i];
            index++;
        }

        return xor ^ index;
    }
}
```

## AND (&) tricks

* selecting certain bits
* reverse the bits in integer

### eg1: BITWISE AND OF NUMBERS RANGE

```java
public class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        if (m == 0) return 0;

        int count = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            count++;
        }

        return m << count;
    }
}
```

### Get all 1-bits \~0eg2: NUMBER OF 1 BITS

```java
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            count += (n & 1);
            n = n >>> 1;
        }

        return count;
    }
}
```

## OR (|) trick

* Keep as many 1-bits as possible

### eg1: Find Largest power of 2

> Find the largest power of 2 (most significant bit in binary form), which is less than or equal to the given number N.

```java
long largest_power(long N) {
    //changing all right side bits to 1.
    N = N | (N>>1);
    N = N | (N>>2);
    N = N | (N>>4);
    N = N | (N>>8);
    N = N | (N>>16);
    return (N+1)>>1;
}
```

### eg2: REVERSE BITS

```java
public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int rst = 0;
        for (int i = 0; i < 32; i++) {
            rst += (n & 1);
            n >>>= 1;
            if (i < 31) rst <<= 1;
        }

        return rst;
    }
}
```


---

# 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://liuyang89116.gitbook.io/my-leetcode-book/post_chapter_2_math/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.