Bit Manipulation

Bit Manipulation #

  • 异或的特性。第 136 题,第 268 题,第 389 题,第 421 题,
x ^ 0 = x
x ^ 11111……1111 = ~x
x ^ (~x) = 11111……1111
x ^ x = 0
a ^ b = c  => a ^ c = b  => b ^ c = a (交换律)
a ^ b ^ c = a ^ (b ^ c) = (a ^ b^ c (结合律)
  • 构造特殊 Mask,将特殊位置放 0 或 1。
 x 最右边的 n 位清零 x & ( ~0 << n )
获取 x 的第 n 位值(0 或者 1)(x >> n) & 1
获取 x 的第 n 位的幂值x & (1 << (n - 1))
仅将第 n 位置为 1x | (1 << n)
仅将第 n 位置为 0x & (~(1 << n))
 x 最高位至第 n ()清零x & ((1 << n) - 1)
将第 n 位至第 0 ()清零x & (~((1 << (n + 1)) - 1)
  • 有特殊意义的 & 位操作运算。第 260 题,第 201 题,第 318 题,第 371 题,第 397 题,第 461 题,第 693 题,
X & 1 == 1 判断是否是奇数(偶数)
X & = (X - 1) 将最低位(LSB) 1 清零
X & -X 得到最低位(LSB) 1
X & ~X = 0
TitleSolutionDifficultyTimeSpace收藏
78. SubsetsGoMediumO(n^2)O(n)❤️
136. Single NumberGoEasyO(n)O(1)
137. Single Number IIGoMediumO(n)O(1)❤️
169. Majority ElementGoEasyO(n)O(1)❤️
187. Repeated DNA SequencesGoMediumO(n)O(1)
190. Reverse BitsGoEasyO(n)O(1)❤️
191. Number of 1 BitsGoEasyO(n)O(1)
201. Bitwise AND of Numbers RangeGoMediumO(n)O(1)❤️
231. Power of TwoGoEasyO(1)O(1)
260. Single Number IIIGoMediumO(n)O(1)❤️
268. Missing NumberGoEasyO(n)O(1)
318. Maximum Product of Word LengthsGoMediumO(n)O(1)
338. Counting BitsGoMediumO(n)O(n)
342. Power of FourGoEasyO(n)O(1)
371. Sum of Two IntegersGoEasyO(n)O(1)
389. Find the DifferenceGoEasyO(n)O(1)
393. UTF-8 ValidationGoMediumO(n)O(1)
397. Integer ReplacementGoMediumO(n)O(1)
401. Binary WatchGoEasyO(1)O(1)
405. Convert a Number to HexadecimalGoEasyO(n)O(1)
421. Maximum XOR of Two Numbers in an ArrayGoMediumO(n)O(1)❤️
461. Hamming DistanceGoEasyO(n)O(1)
476. Number ComplementGoEasyO(n)O(1)
477. Total Hamming DistanceGoMediumO(n)O(1)
693. Binary Number with Alternating BitsGoEasyO(n)O(1)❤️
756. Pyramid Transition MatrixGoMediumO(n log n)O(n)
762. Prime Number of Set Bits in Binary RepresentationGoEasyO(n)O(1)
784. Letter Case PermutationGoEasyO(n)O(1)
898. Bitwise ORs of SubarraysGoMediumO(n)O(1)
————————————————————————————————–———————–———–——–

⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者