2.15 ✅ Bit Manipulation

Bit Manipulation #

  • Properties of XOR。Problem 136,Problem 268,Problem 389,Problem 421,
x ^ 0 = x
x ^ 11111……1111 = ~x
x ^ (~x) = 11111……1111
x ^ x = 0
a ^ b = c  => a ^ c = b  => b ^ c = a (commutative law)
a ^ b ^ c = a ^ (b ^ c) = (a ^ b^ c (associative law)
  • Construct a special Mask,put special positions as 0 or 1。
Clear the rightmost n bits of x x & ( ~0 << n )
Get the nth bit value of x(0 or 1)(x >> n) & 1
Get the power value of the nth bit of xx & (1 << (n - 1))
Set only the nth bit to 1x | (1 << n)
Set only the nth bit to 0x & (~(1 << n))
Clear from the most significant bit of x to the nth bit(inclusive)x & ((1 << n) - 1)
Clear from the nth bit to the 0th bit(inclusive)x & (~((1 << (n + 1)) - 1)
  • & bit operations with special meanings。Problem 260,Problem 201,Problem 318,Problem 371,Problem 397,Problem 461,Problem 693,
X & 1 == 1 determine whether it is odd(even)
X & = (X - 1) clear the 1 in the least significant bit(LSB)
X & -X get the 1 in the least significant bit(LSB)
X & ~X = 0
No.TitleSolutionDifficultyTimeComplexitySpaceComplexityFavoriteAcceptance
0029Divide Two IntegersGoMedium17.2%
0067Add BinaryGoEasy52.4%
0078SubsetsGoMediumO(n^2)O(n)❤️74.9%
0089Gray CodeGoMedium57.2%
0090Subsets IIGoMedium55.9%
0136Single NumberGoEasyO(n)O(1)70.7%
0137Single Number IIGoMediumO(n)O(1)❤️58.5%
0187Repeated DNA SequencesGoMediumO(n)O(1)47.0%
0190Reverse BitsGoEasyO(n)O(1)❤️54.0%
0191Number of 1 BitsGoEasyO(n)O(1)66.6%
0201Bitwise AND of Numbers RangeGoMediumO(n)O(1)❤️42.5%
0231Power of TwoGoEasyO(1)O(1)46.0%
0260Single Number IIIGoMediumO(n)O(1)❤️67.7%
0268Missing NumberGoEasyO(n)O(1)62.6%
0287Find the Duplicate NumberGoMedium59.1%
0318Maximum Product of Word LengthsGoMediumO(n)O(1)59.9%
0338Counting BitsGoEasyO(n)O(n)75.8%
0342Power of FourGoEasyO(n)O(1)46.2%
0371Sum of Two IntegersGoMediumO(n)O(1)50.7%
0389Find the DifferenceGoEasyO(n)O(1)59.9%
0393UTF-8 ValidationGoMediumO(n)O(1)45.1%
0397Integer ReplacementGoMediumO(n)O(1)35.2%
0401Binary WatchGoEasyO(1)O(1)52.3%
0405Convert a Number to HexadecimalGoEasyO(n)O(1)46.8%
0421Maximum XOR of Two Numbers in an ArrayGoMediumO(n)O(1)❤️54.0%
0461Hamming DistanceGoEasyO(n)O(1)75.0%
0473Matchsticks to SquareGoMedium40.2%
0476Number ComplementGoEasyO(n)O(1)67.4%
0477Total Hamming DistanceGoMediumO(n)O(1)52.2%
0491Non-decreasing SubsequencesGoMedium60.2%
0526Beautiful ArrangementGoMedium64.4%
0638Shopping OffersGoMedium53.3%
0645Set MismatchGoEasy42.7%
0693Binary Number with Alternating BitsGoEasyO(n)O(1)❤️61.6%
0756Pyramid Transition MatrixGoMediumO(n log n)O(n)52.7%
0762Prime Number of Set Bits in Binary RepresentationGoEasyO(n)O(1)68.0%
0784Letter Case PermutationGoMediumO(n)O(1)73.8%
0810Chalkboard XOR GameGoHard55.8%
0864Shortest Path to Get All KeysGoHard45.6%
0898Bitwise ORs of SubarraysGoMediumO(n)O(1)37.2%
0980Unique Paths IIIGoHard81.7%
0995Minimum Number of K Consecutive Bit FlipsGoHard51.2%
0996Number of Squareful ArraysGoHard49.2%
1009Complement of Base 10 IntegerGoEasy61.5%
1178Number of Valid Words for Each PuzzleGoHard46.3%
1239Maximum Length of a Concatenated String with Unique CharactersGoMedium52.2%
1310XOR Queries of a SubarrayGoMedium72.3%
1442Count Triplets That Can Form Two Arrays of Equal XORGoMedium76.1%
1461Check If a String Contains All Binary Codes of Size KGoMedium56.6%
1486XOR Operation in an ArrayGoEasy84.6%
1655Distribute Repeating IntegersGoHard39.3%
1659Maximize Grid HappinessGoHard38.8%
1680Concatenation of Consecutive Binary NumbersGoMedium57.0%
1681Minimum IncompatibilityGoHard37.8%
1684Count the Number of Consistent StringsGoEasy82.3%
1720Decode XORed ArrayGoEasy85.8%
1734Decode XORed PermutationGoMedium63.0%
1738Find Kth Largest XOR Coordinate ValueGoMedium61.0%
1763Longest Nice SubstringGoEasy61.5%

Calendar Jun 28, 2026
Edit Edit this page
Total visits:   You are visitor No.
中文