('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
