常见二进制操作

基本操作

a=0^a=a^0

0=a^a

由上面两个推导出：a=a^b^b

交换两个数

a=a^b

b=a^b

a=a^b

移除最后一个 1

a=n&(n-1)

获取最后一个 1

diff=(n&(n-1))^n

判断整数的奇偶性

if((n & 1) == 0)

乘以2操作

n << 1

向下整除

n >> 1

只出现一次的数字

Leetcode：136.只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

1
2
输入：nums = [2,2,1]
输出：1

思路：相同的两个数异或会变成0，所以让所有数进行异或，剩下的数就是需要的元素

1
2
3
4
5
6
7
8
func singleNumber(nums []int) int {
    res := 0
    for _, v := range nums {
        res ^= v
    }

    return res
}

只出现一次的数字 II

Leetcode：137. 只出现一次的数字 II

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

1
2
输入：nums = [2,2,3,2]
输出：3

思路：

  • 方法一：使用哈希表

  • 方法二：出现3次的数字的位加起来为3，所以这个位对3求余为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func singleNumber(nums []int) int {
    res := 0

    // 先处理所有数字的第0个位，找出仅出现一次的元素的第0个位，再处理所有数字第1个位.....
    for i := 0; i < 32; i++ {
        total := 0
        for _, v := range nums {
            total += v >> i & 1 // 累加保存每一个位的值
        }

        if total % 3 > 0 {    // 未能对3求余的值就是只出现一次的值的位
            res |= 1 << i	// 对1进行左移i个位，然后用后操作加到res里
        }
    }

	return res
}

只出现一次的数字 III

Leetcode：260. 只出现一次的数字 III

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例 1：

1
2
3
输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

思路：首先把所有元素异或，得到result，这个result就是只出现一次的两个元素的异或；

然后取出这个result中最低位为1的值，设为L，那么这两个不同的元素中某一个元素的二进制表示的第L位为0，另一个元素第L位为1，这样两个数异或的第L位才能为1；

这样一来，我们就可以把所有元素分成两类，其中一类包含所有二进制表示的第L位为0的数，另一类包含所有二进制表示的第L位为1的数。可以发现：

  • 对于任意一个在数组中出现两次的元素，该元素的两次出现会被包含在同一类中；

  • 对于任意一个在数组中只出现了一次的元素，它们会被包含在不同类中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func singleNumber(nums []int) []int {
    result := 0
    for _, v := range nums {
        result ^= v // result的值其实就是只出现一次的两个元素的异或
    }

    // 从result中找出等于1的一个位，等于1的位，说明两个元素在这个位是不一样的
    div := 1
    for div & result == 0 {
        div <<= 1
    }

    // 分组
    a, b := 0, 0
    for _, v := range nums {
        if div & v == 0 {
            a ^= v
        } else {
            b ^= v
        }
    }
    return []int{a, b}
}

位1的个数

Leetcode：191. 位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数。

示例 1：

1
2
3
输入：n = 00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
1
2
3
4
5
6
7
8
9
10
func hammingWeight(num uint32) int {
    res := 0
    for i := 0; i < 32; i++ {
        if num & 1 == 1 {
            res++
        }
        num >>= 1
    }
    return res
}

优化版本：令num &= num - 1，这个操作能让最右边的1会被抹去变成0，重复操作，最终num的二进制表示的最后一个1变成0

1
2
3
4
5
6
7
8
func hammingWeight(num uint32) int {
    res := 0
    for num != 0 {
        num &= num - 1
        res++
    }
    return res
}

颠倒二进制位

Leetcode：190. 颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

1
2
3
4
5
6
7
8
9
10
11
12
func reverseBits(num uint32) uint32 {
    res := uint32(0)
    pow := 31

    for num != 0 {
        res |= (num & 1) << pow // 先取出最低位，然后左移，放到res里
        num >>= 1   // 丢弃已经处理过的位
        pow--
    }

    return res
}

数字范围按位与

Leetcode：201. 数字范围按位与

给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。

示例 1：

1
2
输入：left = 5, right = 7
输出：4

思路：目的是求出两个给定数字的二进制字符串的公共前缀，这里给出的第一个方法是采用位移操作。想法是将两个数字不断向右移动，直到数字相等，即数字被缩减为它们的公共前缀。然后，通过将公共前缀向左移动，将零添加到公共前缀的右边以获得最终结果。

1
2
3
4
5
6
7
8
func rangeBitwiseAnd(m int, n int) int {
    shift := 0
    for m < n {
        m, n = m >> 1, n >> 1
        shift++
    }
    return m << shift
}

实现乘法运算

如何不用任何运算符计算两个正整数的乘积？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func multiplication(a, b int) int {
	// 判断正负，同时把a和b都转成正数计算
	sign := 1
	if a < 0 {
		sign = -sign
		a = -a
	}
	if b < 0 {
		sign = -sign
		b = -b
	}

	res := 0
	for b > 0 {
		if b&1 == 1 { // 奇数，结果加一个a，b减1变成偶数
			res += a
		}
		a <<= 1
		b >>= 1
	}
	return res * sign
}