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

# Bit Manipulation

## 消去`二进制`中最右侧的那个“1”

```java
x & (x - 1) // 消去 x 最后一位的 1，比如 x = 12，那么在二进制下就是 (1100)2

x           = 1100
x - 1       = 1011
x & (x - 1) = 1000
```

### LintCode: 142. O(1) Check Power of 2

> Using `O(1)` time to check whether an integer `n` is a power of `2`.

满足要求的N有两个条件：

1. N > 0
2. N 的二进制表示**有且只有**一个`1`

所以用“技巧一”可以写出如下`Java`代码

{% code title="Check\_Power\_of\_2" %}

```java
public class Solution {
    /**
     * @param n: An integer
     * @return: True or false
     */
    public boolean checkPowerOf2(int n) {
        // write your code here
        return (n > 0) && ((n & (n - 1)) == 0);
    }
}
```

{% endcode %}

### LintCode: 365. Count 1 in Binary

> Count how many `1` in binary representation of a 32-bit integer.

上一道题目的变体咯，既然要看有多少个1，那我就一直算下去，直到它变成0

{% code title="Count\_1\_in\_Binary" %}

```java
public class Solution {
    /*
     * @param num: An integer
     * @return: An integer
     */
    public int countOnes(int num) {
        // write your code here
        int count = 0;
        while (num != 0) {
            num = num & (num - 1);
            count++;
        }
        return count;
    }
};
```

{% endcode %}

### LintCode: 181. Flip Bits

> Determine the number of bits required to flip if you want to convert integer `n` to integer `m`.

#### Solution 1

{% code title="Flip\_Bits" %}

```java
public class Solution {
    /**
     * @param a: An integer
     * @param b: An integer
     * @return: An integer
     */
    public int bitSwapRequired(int a, int b) {
        // write your code here
        String bit = Integer.toBinaryString(a ^ b);
        int num = 0;
        for (int i = 0; i < bit.length(); i++) {
            num += (bit.charAt(i) - '0');
        }
        return num;
    }
}
```

{% endcode %}

#### Solution 2

```java
class Solution {
    /**
     *@param a, b: Two integer
     *return: An integer
     */
    public int countOnes(int num) {
        int count = 0;
        while (num != 0) {
            num = num & (num - 1);
            count++;
        }
        return count;
    }

    public int bitSwapRequired(int a, int b) {
        // write your code here
        return countOnes(a ^ b);
    }
};
```

#### Solution 3

```java
/**
* 本参考程序来自九章算法，由 @九章算法 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

class Solution {
    /**
     *@param a, b: Two integer
     *return: An integer
     */
    public static int bitSwapRequired(int a, int b) {
        // write your code here
        int count = 0;  
        for (int c = a ^ b; c != 0; c = c >>> 1) {
            count += c & 1;
        }
        return count;
    }
};
```

## 巧用`异或XOR`运算

```java
a ^ b ^ b = a  // 对一个数异或两次等价于没有任何操作
```

### LintCode: 82. Single Number

> Given `2*n + 1` numbers, every numbers occurs twice except one, find it.

#### `XOR` Operator

* `O(n)` Time
* `O(1)` Space

{% code title="Single\_Number" %}

```java
public class Solution {
    /**
     * @param A: An integer array
     * @return: An integer
     */
    public int singleNumber(int[] A) {
        // write your code here
        int result = 0, n = A.length;
        for (int i = 0; i < n; i++) {
            result ^= A[i];
        }
        return result;
    }
}
```

{% endcode %}

#### Python `collections.Counter()`

* `O(n)` Time **at least**
* `O(n)` Space

{% code title="Single\_Number" %}

```python
class Solution:
    """
    @param A: An integer array
    @return: An integer
    """
    def singleNumber(self, A):
        # write your code here
        dict = collections.Counter(A)
        for key in dict:
            if dict[key] == 1:
                return key
```

{% endcode %}

## 将两个数不同的位设置为“1”，其余为“0”

```java
int bitFlag = (AXORB & (~ (AXORB - 1)));
```

> 这一行代码的作用是：找到数字 `A` 和数字 `B` 中不相同的一位，并将该位设置为 `1`，其他位设置为 `0`；\
> `根据 XOR 的定义，我们知道，在 AXORB 中，为 1 的位即 A 和 B 不相同的位，AXORB 中为 0 的位即 A 和 B 中相同的位`\
> 所以，要找到 `A` 和 `B` 中不相同的位，只需要找到在 `AXORB` 中从右往左第一个为 `1` 的位，保留该位并将其他位置为 `0` 即可。

### [LeetCode: 260. Single Number III](https://leetcode.com/problems/single-number-iii/description/)

```java
public class Solution {
    public int[] singleNumber(int[] nums) {
        int AXORB = 0;
        for (int num : nums) {
            AXORB ^= num; 
        }
        // pick one bit as flag
        int bitFlag = (AXORB & (~ (AXORB - 1)));
        int[] res = new int[2];
        for (int num : nums) {
            if ((num & bitFlag) == 0) {
                res[0] ^= num;
            } else {
                res[1] ^= num;
            }
        }
        return res;
    }
}
```

> 假设数组中两个不同的数字为 A 和 B；
>
> 1. 通过遍历整个数组并求整个数组所有数字之间的 XOR，根据 XOR 的特性可以得到最终的结果为 `AXORB = A XOR B`；
> 2. 通过某种特定的方式，我们可以通过 AXORB 得到在数字 A 和数字 B 的**二进制**下某一位不相同的位；**因为A 和 B 是不相同的，所以他们的二进制数字有且至少有一位是不相同的**。我们将这一位设置为 1，并将所有的其他位设置为 0，我们假设我们得到的这个数字为 `bitFlag`；
> 3. 那么现在，我们很容易知道，数字 A 和 数字 B 中`必然有一个数字与上 bitFlag 为 0`；因为`bitFlag` 标志了数字 A 和数字 B 中的某一位不同，那么在数字 A 和 B 中的这一位必然是**一个为 0，另一个为 1**；而我们在 bitFlag 中将其他位都设置为 0，那么**该位为 0 的数字与上 bitFlag 就等于 0，而该位为 1 的数字与上 bitFlag 就等于 bitFlag**
> 4. 现在问题就简单了，我们只需要在循环一次数组，将与上 `bitFlag` 为 0 的数字进行 `XOR` 运算，与上 `bitFlag` 不为 0 的数组进行独立的 XOR 运算。那么最后我们得到的这两个数字就是 `A` 和 `B`。