第一次算法分享——2道简单的位运算试题

1. 已知一个数组中所有的数字都出现了2次，但只有一个数字只出现了1次，请找出这个数字

解题思路：

由于异或运算满足交换律，且符合

k ^ k = 0

0 ^ k = k

考虑将数组中的每一个元素与前一个元素进行异或运算，最后“剩下”的那个数即为所求。

具体代码：

func singleNumber(nums []int) (ans int) {
    ans = 0
    for _, v := range nums {
        ans ^= v 
    }
    return
}

2. 请计算n的二进制表达中出现了多少个1 （  0 < n < 2 ** 32 )

具体题面：

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

提示：

• 输入必须是长度为 32 的 二进制串 。

解题思路：

由于输入是一个32位的二进制串，考虑让每一位与1作“与运算”来得到1的个数，然后把整个数字右移1位来把刚才运算过的那一位给“删去”。

具体代码：

func hammingWeight(n uint32) (count int) {
    for i := 0; i < 32; i++ {
        if n & 1 == 1 {
            count++
        }
        n >>= 1;
    }
    return
}

附录：

位运算法则参考

以上是我的算法刷题中的两道比较经典的简单位运算试题。