Day 76 位运算: 1356. 根据数字二进制下 1 的数目排序

('a' | ' ') = 'a'
('A' | ' ') = 'a'
('b' & '_') = 'B'
('B' & '_') = 'B'
('d' ^ ' ') = 'D'
('D' ^ ' ') = 'd'
不用临时变量交换两个数
int a = 1, b = 2;
a ^= b;
b ^= a;
a ^= b;
// 现在 a = 2, b = 1
加一
int n = 1;
n = -~n;
// 现在 n = 2
减一
int n = 2;
n = ~-n;
// 现在 n = 1
判断两个数是否异号
int x = -1, y = 2;
boolean f = ((x ^ y) < 0); // true
int x = 3, y = 2;
boolean f = ((x ^ y) < 0); // false
利用的是补码编码的符号位。整数编码最高位是符号位，负数的符号位是 1，非负数的符号位是 0，再借助异或的特性，可以判断出两个数字是否异号。

n & (n-1) 的运用
n & (n-1) 这个操作在算法中比较常见，作用是消除数字 n 的二进制表示中的最后一个 1。

191. Number of 1 Bits

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n != 0:
            n = n & (n-1)
            res += 1
        return res

231. Power of Two

一个数如果是 2 的指数，那么它的二进制表示一定只含有一个 1.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False 
        return (n & (n-1)) == 0

a ^ a = 0 的运用

一个数和它本身做异或运算结果为 0，即 a ^ a = 0；一个数和 0 做异或运算的结果为它本身，即 a ^ 0 = a。

136. Single Number

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for i in range(len(nums)):
            res = res ^ nums[i] 
        return res

268. Missing Number

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums) 
        res = n
        for i in range(n):
            res = res ^ (i ^ nums[i])
        return res

1356. 根据数字二进制下 1 的数目排序

思路
- example
- 计算每个数字的二进制含1的个数，然后按此排序（先含1个数大小，后数值本身大小）
复杂度. 时间：O(), 空间: O()

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        def countOne(num):
            res = 0
            while num:
                if num % 2 == 1:
                    res += 1
                num = num // 2 
            return res  
        arr.sort(key=lambda num: (countOne(num), num))  
        return arr

位运算

n = n & (n-1) # 清除最低位的1

class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        def countOnes(num):
            res = 0
            while num != 0:
                num = num & (num-1)
                res += 1
            return res  
        arr.sort(key=lambda x: (countOnes(x), x))
        return arr

最后编辑于：2023.04.09 04:46:34