('a' | ' ') = 'a'
('A' | ' ') = 'a'
('b' & '_') = 'B'
('B' & '_') = 'B'
('d' ^ ' ') = 'D'
('D' ^ ' ') = 'd'
不用臨時(shí)變量交換兩個(gè)數(shù)
int a = 1, b = 2;
a ^= b;
b ^= a;
a ^= b;
// 現(xiàn)在 a = 2, b = 1
加一
int n = 1;
n = -~n;
// 現(xiàn)在 n = 2
減一
int n = 2;
n = ~-n;
// 現(xiàn)在 n = 1
判斷兩個(gè)數(shù)是否異號(hào)
int x = -1, y = 2;
boolean f = ((x ^ y) < 0); // true
int x = 3, y = 2;
boolean f = ((x ^ y) < 0); // false
利用的是補(bǔ)碼編碼的符號(hào)位。整數(shù)編碼最高位是符號(hào)位，負(fù)數(shù)的符號(hào)位是 1，非負(fù)數(shù)的符號(hào)位是 0，再借助異或的特性，可以判斷出兩個(gè)數(shù)字是否異號(hào)。

n & (n-1) 的運(yùn)用
n & (n-1) 這個(gè)操作在算法中比較常見(jiàn)，作用是消除數(shù)字 n 的二進(jìn)制表示中的最后一個(gè) 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

一個(gè)數(shù)如果是 2 的指數(shù)，那么它的二進(jìn)制表示一定只含有一個(gè) 1.

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

a ^ a = 0 的運(yùn)用

一個(gè)數(shù)和它本身做異或運(yùn)算結(jié)果為 0，即 a ^ a = 0；一個(gè)數(shù)和 0 做異或運(yùn)算的結(jié)果為它本身，即 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. 根據(jù)數(shù)字二進(jìn)制下 1 的數(shù)目排序

• 思路
  • example
  • 計(jì)算每個(gè)數(shù)字的二進(jìn)制含1的個(gè)數(shù)，然后按此排序 （先含1個(gè)數(shù)大小，后數(shù)值本身大?。?/li>
• 復(fù)雜度. 時(shí)間：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 

• 位運(yùn)算

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