chapter5-bit-operation-algorithm

chapter5-bit-operation-algorith

[TOC]

位运算

1.统计两个数的二进制表示有多少位不同

# 461. 汉明距离
import math
def hammingDistance():
    x = 1; y = 4
    # 1:(0 0 0 1); 4:(0 1 0 0)
    # 有上述列子可知，根据题意，我们把两个数算异或就可以知道那些位置不一样了
    # 1 ^ 4->(0 1 0 1)->5
    # 然后遍历得到数字，每次取一位数，判断是否为1，如果是1 那就是不一样计数即可。
    cnt, z = 0, x ^ y
    print(z)
    while(z != 0):
        # if (z & 1) == 1:
        #     cnt += 1

        # cnt += z&1
        # z = z >> 1
        z &= (z - 1)
        cnt += 1
    print(cnt)
    return cnt
hammingDistance()

2.数组中唯一一个不重复的元素

# 136. 只出现一次的数字
def singleNumber():
    nums = [2,2,1]
    cnt = 0
    # 初始化一个不存在的数，依次进行异或运算，最后得到的数就为不存在的数
    # 因为相同抵消，不相同继承
    for v in nums:
        cnt ^= v
        print(cnt)
    return cnt
singleNumber()

3. 找出数组中缺失的那个数

# 268. 缺失数字
def missingNumber():
    nums = [3,0,1]
    # 由136. 只出现一次的数字解题思路，更加升华一层
    # 异或：如果初始化数为cnt = 0的话，每一个数n对cnt进行异或运算，
    # 那么如果n出现的次数是偶数，那还是会回到cnt最初的值
    # 那么如果n出现的次数是奇数，那将会出现n是奇数的那个数值
    # 因此代码逻辑如下：
    cnt = 0
    for i, n in enumerate(nums):
        cnt = cnt ^ i ^ n
    print(cnt ^ len(nums))
    return cnt^ len(nums)

4. 数组中不重复的两个元素

# 260. 只出现一次的数字 III
def singleNumber1():
    nums = [1,2,1,3,2,5]
    # 继承 268. 缺失数字 异或算法的思路
    # 我们能够找到两个只出现一次数之间的异或运算
    # 现在的问题是我们如何进行区分这两个数
    # 由于两个不相等的元素在位级表示上必定会有一位存在不同
    # diff &= -diff 得到出 diff 最右侧不为 0 的位，也就是不存在重复的两个元素在位级表示上最右侧不同的那一位，
    # 利用这一位就可以将两个元素区分开来。
    # 比如3(11)^5(101)->(6)110:其中通过观察第二为bit不同也就是2(10)
    # 那如何通过得到(6)110去得到这一位不同的数呢！
    # 6的正数的补码就是本身(1110)->最高位符号位，对于负数呢？
    # 就是符号位为0，且除符号位外，进行反码(0001)，然后加1就得到负数(0010)，即-6的补码形式(0010)
    # 因此只需要进行相互求并集，就可以得到不同的位了->(1110 & 0010 = 10)
    # 即公式为：diff &= -diff
    # 最后代码逻辑如下：
    diff = 0
    for n in nums:
        diff ^= n
    print(bin(diff),bin(-diff))
    diff &= -diff
    print(diff)
    res = [0, 0]
    for n in nums:
        if n & diff == 0:
            res[0] ^= n
        else:
            res[1] ^= n
    print(res)
    return res
singleNumber1()

5. 翻转一个数的比特位

def reverseBits():
    # 根据题意 以及栗子观察可得
    # 每次取n的末位数，与初始化0的res末位数进或运输，就能够使最后一位数，变成第一位数，实现反转
    # 每次是res向左移动一位，就是增加一位，使n向右移动一位，就是减少一位，每一位求或就实现了最终的反转
    res, n = 0, 43261596
    for i in range(32):
        res <<= 1
        res |= (n & 1)
        n >>= 1
    print(res)
    return res
reverseBits()

6. 不用额外变量交换两个整数

ef transer_nums():
    a, b = 3, 8
    a = a ^ b
    b = a ^ b
    a = a ^ b
    print(a,b)

7. 判断一个数是不是 2 的 n 次方

def isPowerOfTwo():
    n = 16
    # 要是一个2的n次方的数
    # 特点如下：1.二进制中只有一个1 2. (n & n-1)== 0 -> 1000 & 0111 == 0
    print(n > 0 and (n & n-1)==0)
    return n > 0 and (n & n-1)==0
 isPowerOfTwo()

8. 判断一个数是不是 4 的 n 次方

def isPowerOfFour():
    # 要是一个4的n次方的数
    # 特点如下：1.二进制中只有一个1，且在奇数位上 2. (n & n-1)== 0 -> 1000 & 0111 == 0
    num = 16
    def slove():
        print(num > 0 & (num & (num - 1)) == 0  & (num & 0xaaaaaaaa) == 0)
        print(num > 0 & (num & (num - 1)) == 0  & (num % 3 == 1))
        return num > 0 & (num & (num - 1)) == 0 & (num & 0xaaaaaaaa) == 0


    # 对于x = 4^n-> n = log_4^x -> 0.5log_2^x
    # 因此代码逻辑如下：
    def slove1():
        return num > 0 and math.log(num,2) % 2 == 0

    slove()
    slove1()
isPowerOfFour()

9. 判断一个数的位级表示是否不会出现连续的 0 和 19.

# 693. 交替位二进制数
def hasAlternatingBits():
    n = 5
    # 对于不连续的数来说, 1010>>1->101
    # 有1010^101=1111
    a = n ^ (n >> 1)
    print(a)
    return (a & (a + 1)) == 0
hasAlternatingBits()

10. 求一个数的补码

def findComplement():
    num = 5

    def slove():
        # 给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。
        # 对于 00001101，要求补码可以将它与 00001111 进行异或操作。那么问题就转换为求掩码 00001111。
        # 代码逻辑如下
        if num == 0:
            return 1
        mask = 1 << 30
        # 找到第一位是1的数，如上mask=1000
        while num & mask == 0:
            mask >>= 1
        mask = (mask<<1) - 1 #得到掩码
        print(num ^ mask)
        return num ^ mask

    def slove2():
        # 同上补码= 00001111-00001101
        temp = 1
        #反向去找第一个1,因为最后一部分全为0，没有符号位置或者没有
        while (num >= temp):
            temp <<= 1
        print(temp)
        return (temp - 1 - num)

    slove()
    slove2()
findComplement()

11. 实现整数的加法

# 338. 比特位计数
def countBits():
    num = 5
    # 在二进制中，有1的存在，必定是在2^n位置，
    # 因此只需要在每次有出现1的地方加1即可，其他的位置继承上一次位置就行。
    # 在这利用dp[i&(i-1)]公式，使得这次的位置总是指向上一次出现2^n的位置
    dp = [0 for i in range(num+1)]
    for i in range(1,num + 1):
        dp[i] = dp[i&(i-1)] +1
    print(dp)
    return dp