# 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`。


---

# 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://lintcode-solutions.gitbook.io/project/cs-fundamentals/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.