2.15 ✅ 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
No.TitleSolutionDifficultyTimeComplexitySpaceComplexityFavoriteAcceptance
0029Divide Two IntegersGoMedium17.4%
0067Add BinaryGoEasy51.0%
0078SubsetsGoMediumO(n^2)O(n)❤️73.1%
0089Gray CodeGoMedium56.1%
0090Subsets IIGoMedium54.7%
0136Single NumberGoEasyO(n)O(1)69.9%
0137Single Number IIGoMediumO(n)O(1)❤️57.4%
0187Repeated DNA SequencesGoMediumO(n)O(1)45.8%
0190Reverse BitsGoEasyO(n)O(1)❤️51.1%
0191Number of 1 BitsGoEasyO(n)O(1)63.7%
0201Bitwise AND of Numbers RangeGoMediumO(n)O(1)❤️42.1%
0231Power of TwoGoEasyO(1)O(1)45.4%
0260Single Number IIIGoMediumO(n)O(1)❤️67.3%
0268Missing NumberGoEasyO(n)O(1)61.1%
0287Find the Duplicate NumberGoMedium59.0%
0318Maximum Product of Word LengthsGoMediumO(n)O(1)60.2%
0338Counting BitsGoEasyO(n)O(n)74.9%
0342Power of FourGoEasyO(n)O(1)45.4%
0371Sum of Two IntegersGoMediumO(n)O(1)50.6%
0389Find the DifferenceGoEasyO(n)O(1)60.5%
0393UTF-8 ValidationGoMediumO(n)O(1)39.4%
0397Integer ReplacementGoMediumO(n)O(1)35.0%
0401Binary WatchGoEasyO(1)O(1)51.2%
0405Convert a Number to HexadecimalGoEasyO(n)O(1)46.0%
0421Maximum XOR of Two Numbers in an ArrayGoMediumO(n)O(1)❤️54.6%
0461Hamming DistanceGoEasyO(n)O(1)74.7%
0473Matchsticks to SquareGoMedium40.6%
0476Number ComplementGoEasyO(n)O(1)67.0%
0477Total Hamming DistanceGoMediumO(n)O(1)52.1%
0491Increasing SubsequencesGoMedium51.7%
0526Beautiful ArrangementGoMedium64.6%
0638Shopping OffersGoMedium54.6%
0645Set MismatchGoEasy41.4%
0693Binary Number with Alternating BitsGoEasyO(n)O(1)❤️61.1%
0756Pyramid Transition MatrixGoMediumO(n log n)O(n)53.7%
0762Prime Number of Set Bits in Binary RepresentationGoEasyO(n)O(1)67.4%
0784Letter Case PermutationGoMediumO(n)O(1)73.2%
0810Chalkboard XOR GameGoHard54.7%
0864Shortest Path to Get All KeysGoHard45.3%
0898Bitwise ORs of SubarraysGoMediumO(n)O(1)36.5%
0980Unique Paths IIIGoHard79.5%
0995Minimum Number of K Consecutive Bit FlipsGoHard51.1%
0996Number of Squareful ArraysGoHard49.1%
1009Complement of Base 10 IntegerGoEasy62.1%
1178Number of Valid Words for Each PuzzleGoHard46.6%
1239Maximum Length of a Concatenated String with Unique CharactersGoMedium50.6%
1310XOR Queries of a SubarrayGoMedium71.9%
1442Count Triplets That Can Form Two Arrays of Equal XORGoMedium75.4%
1461Check If a String Contains All Binary Codes of Size KGoMedium56.8%
1486XOR Operation in an ArrayGoEasy84.1%
1655Distribute Repeating IntegersGoHard39.7%
1659Maximize Grid HappinessGoHard38.3%
1680Concatenation of Consecutive Binary NumbersGoMedium52.5%
1681Minimum IncompatibilityGoHard37.5%
1684Count the Number of Consistent StringsGoEasy81.9%
1720Decode XORed ArrayGoEasy85.9%
1734Decode XORed PermutationGoMedium61.8%
1738Find Kth Largest XOR Coordinate ValueGoMedium61.8%
1763Longest Nice SubstringGoEasy61.8%
——————————————————————-——-—————-—————————-————-————-

⬅️上一页

下一页➡️

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