LeetCode-算法-位运算-第14天

190. 颠倒二进制位

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

示例 1：
输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
示例 2：
输入：11111111111111111111111111111101
输出：10111111111111111111111111111111
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
示例 1：
输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。
示例 2：
输入：n = 11111111111111111111111111111101
输出：3221225471 (10111111111111111111111111111111)
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。

具体题目链接

Python

class Solution:
    def reverseBits(self, n: int) -> int:
        rev=0
        for i in range(0,32):
            rev|=(n&1)<<(31-i)
            n >>= 1
        return rev

思路：for i in range(0,32)表示循环次数32次。(n&1)之前了解过，只保留当前n最右侧一位，(n&1)<<(31-i),的意思是将最右侧一位左移(31-i)。此时rev按位|与，从而使最高位获取到n最右侧一位。同理，第二次循环则是左侧第二位获取n的右侧第二位。
这里以8位的二进制，则相对应的为(n&1)<<(7-i)来举个例子：
第一次循环n=181二进制1011 0101,n&1=0000 0001,通过左移位7位，可以看出变为1000 0000，此处的1是1011 0101的最后一位的1。最后rev 0000 0000 与1000 0000按位与，则rev=1000 0000。之后n=n>>1=0101 1010。
第二次循环n&1=0000 0000通过左移7-i=6位，则变为0000 0000，最后与rev 1000 0000按位与则rev=1000 0000，n=n>>1=0010 1101。最终通过循环结束得到rev为1010 1101。

GO

func reverseBits(num uint32) uint32 {
    // for i:=0;i<32;i++{
    //     k|=(num&1)<<(31-i)
    //     num>>=1
    // }
    // return k
    var m1 uint32=0x55555555 // 01010101010101010101010101010101
    var m2 uint32=0x33333333 // 00110011001100110011001100110011
    var m4 uint32=0x0f0f0f0f // 00001111000011110000111100001111
    var m8 uint32=0x00ff00ff // 00000000111111110000000011111111
    // var m16 uint32=0x0000ffff
    num=((num>>1)&m1)|((num&m1)<<1)
    num=((num>>2)&m2)|((num&m2)<<2)
    num=((num>>4)&m4)|((num&m4)<<4)
    num=((num>>8)&m8)|((num&m8)<<8)
    return num>>16|num<<16
}

思路：分治法，看到这个思路着实给我当头一击，还能这样玩。
我先简单整理一下思路，以整数为例。刚开始为
12345678，通过奇数位与偶数位互换则变为21436587
再通过两个两个互换得到43218765
再通过四个四个互换得到87654321
这里采用8位的数字演示一下，方便理解。此时定义，num=191，二进制位1011 1111（思路：二进制是从左向右看）

    var m1 uint32=0b01010101
    var m2 uint32=0b00110011
    var m4 uint32=0b00001111

先解释一下每一步的作用，以m1举例:
num=((num>>1)&m1)|((num&m1)<<1)
(num>>1)=0101 1111使二进制向右挪动一位，则第一位变为第二位，第二位变成第三位依次类推，实现挪位。
(num>>1)&m1=0101 0101，因为m1是奇数位0，偶数位1，则在进行&操作，只会保留(num>>1)偶数位。
(num&m1)=0001 0101，同理也是只保留num的偶数位。
(num&m1)<<1=0010 1010,因为已知(num&m1)保留了偶数位，通过<<1(左移一位)是其变为只保留奇数位。

因此((num>>2)&m1)|((num&m1)<<2)=0111 1111，此时与1011 1111对比发现，奇偶互换。
同理，num=((num>>2)&m2)|((num&m2)<<2)则等于1101 1111
同理，num=((num>>4)&m4)|((num&m4)<<4)则等于1111 1101
此时num就变为倒序二进制num，因此32位同理，只是增加了8位互换，和16位互换。为什么最后只有
return num>>16|num<<16，而不是像m1 m2一样。原因：因为uint32最高也就32位，也就是左移和右移16位，都会保留下来需要的16位，其余全部为0。而对于python则必须像m1 m2那样，因为python会在左移16位后扩充到int变为64位，使结果错误，因此需要采用限制。

136. 只出现一次的数字

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

示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4

具体题目链接

Python

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return functools.reduce(lambda x,y:x^y,nums)

思路：这里采取官网的三个性质。
1.任何数和 0做异或运算，结果仍然是原来的数，即 a^0=a^0=a。
2.任何数和其自身做异或运算，结果是0，即 a^a=0。
3.异或运算满足交换律和结合律，即 a ^b^a=b^a^a=b^(a^a)=b^0=b。
有了以上性质题目就很好理解了，我们至于要按顺序左异或即可，最终结果就是一个的元素。

GO

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

思路：见python性质。