Bit operation

136. A number that appears only once

class Solution {
    
    public int singleNumber(int[] nums) {
    
        int res = 0;
        for (Integer i : nums) res ^= i;
        
        return res;
    }
}

67. Binary sum

Method 1 ： simulation

class Solution:
    def addBinary(self, a: str, b: str) -> str:  
        m, n, res, carry = len(a), len(b), [], 0
        x = max(m, n)

        for i in range(-1, -x-1, -1):
        	#  Bitwise summation  +  carry , and  2  The remainder of is the result of the current bit , and  2  Take quotient as carry .
            carry += (int(a[i]) if -i <= m else 0) + (int(b[i]) if -i <= n else 0)
            res.append(str(carry % 2))
            carry //= 2

        if carry > 0: #  Add carry 
            res.append('1')

        return ''.join(res[::-1])

        # return bin(int(a, 2) + int(b, 2))[2:]
        # return '{:b}'.format(int(a, 2) + int(b, 2))

Method 2 ： An operation

If addition, subtraction, multiplication and division are not allowed , Bit operations can be used to replace some of the above operations .

class Solution:
    def addBinary(self, a, b) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            answer = x ^ y
            carry = (x & y) << 1
            x, y = answer, carry
        return bin(x)[2:]

137. A number that appears only once II

Method 1 ： Count every binary bit

Use bitwise operation (x >> i) & 1 obtain x Of the i Binary bits , And add them together and then pair them 3 Remainder , The result must be 0 or 1, That's the... Of the answer i Binary bits .

It should be noted that , If the language used is right 「 Signed integer type 」 and 「 Unsigned integer type 」 There is no distinction , Then you may get the wrong answer . This is because 「 Signed integer type 」（ namely int type ） Of the 31 Binary bits （ That is, the highest position ） Is a sign bit in the sense of complement , Corresponding $-2^{31}$ , and 「 Unsigned integer type 」 Because there is no symbol , The first 31 Two bits correspond to $2^{31}$ .Python It is necessary to make special judgment on the highest position in .

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            total = sum((num >> i) & 1 for num in nums)
            if total % 3: 
                # Python  Special judgment is required for the highest position 
                if i == 31:
                    ans -= (1 << i)
                else:
                    ans |= (1 << i)
        return ans

190. Invert binary bit

Method 1 ： Bit by bit

take n As a long as 32 Binary string of , Enumerate from low to high n Every one of them , Add it to the flip result in reverse order $\text{rev}$ in .
Each bit enumerated will n Moves to the right one , So the current n The lowest bit of is the bit to be enumerated . When n by 0 The cycle ends when .

class Solution:
    def reverseBits(self, n: int) -> int:
        # rev = 0
        # for i in range(32):
        # if n != 0:
        # # n  Binary end number of , Joining together to  res  The beginning of , Moving is  n  At the end of the number .
        # rev |= (n & 1) << (31 - i)
        # n >>= 1
                        
        # return rev

        res = 0
        for i in range(32):
            # res  Move left , hold  n  Binary end number of , Splice to result  res  At the end of . then  n  Move right .
            res = (res << 1) | (n & 1)
            n >>= 1
        return res

191. position 1 The number of

stay Python In language , Use bin() Function can get an integer binary string .

One 、 Library function

class Solution(object):
    def hammingWeight(self, n):
        return bin(n).count("1")

Two 、 Move right 32 Time

n & 1 Get the binary end number ; hold n Move right 1 position , Until the end .

class Solution(object):
    def hammingWeight(self, n):
        res = 0
        while n:
            res += n & 1
            n >>= 1
        return res

231. 2 The power of

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return not n & (n - 1) and n > 0
        return n & (-n) == n

260. A number that appears only once III

    def singleNumber(self, nums: List[int]) -> List[int]:
        xor = 0
        for i in nums:
            xor ^= i
        
        lb = xor & -xor #  Far right  1, For grouping .
        x = y = 0
        for i in nums:
            if lb & i:
                x ^= i
            else:
                y ^= i
        return [x, y]

268. Missing numbers

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        ##  Method 1 ： Sort 
        # n = len(nums)
        # nums.sort()
        # for i in range(n):
        # if nums[i] != i:
        # return i
        # return n

        ##  Method 2 ： Hashtable 
        # hash = set(nums)
        # for i in range(len(nums) + 1):
        # if i not in hash:
        # return i

        ##  Method 3 ： Bad 
        # return sum(range(len(nums) + 1)) - sum(nums)
        # return (n := len(nums)) * (n + 1) // 2 - sum(nums)

        ##  Method four ： Exclusive or 
        res = 0
        for i, num in enumerate(nums):
            res ^= i ^ num

        res ^= len(nums)

        return res

318. Maximum word length product

words[i] Use one 32 Binary digit representation , Binary bit number [0, 25] position , They correspond to each other [a, z], Use bit operation to judge two characters words[i] and words[j] Is there a public letter .

transformation : abd => 00000…1011 => 11(10 It's binary 11)
Judge common letters : abd & b => 1011 & 0010 != 0

Method 1 ：set

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        s = [set(w) for w in words]
        ans, n = 0, len(words)
        for i in range(n):            
            for j in range(i + 1, n):
                if not s[i] & s[j]:
                    ans = max(ans, len(words[i]) * len(words[j]))

        return ans

Method 2 ： An operation

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        res, n = 0, len(words)       
        wordArr = [0] * n
        for i, word in enumerate(words):           
            for ch in set(word):
                wordArr[i] |= (1 << (ord(ch)-ord('a'))) 
     
        for i in range(n):
            for j in range(i + 1, n):             
                if (wordArr[i] & wordArr[j]) == 0:
                    res = max(res, len(words[i]) * len(words[j]))

        return res
        ## reduce  List derivation 
        masks = [reduce(lambda a, b: a | (1 << (ord(b) - ord('a'))), word, 0) for word in words]
        return max((len(x[1]) * len(y[1]) for x, y in product(zip(masks, words), repeat=2) if x[0] & y[0] == 0), default=0)

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        def hashset(word):
            #  use  32  Bit binary number means  word, Also is to   String mapping   To   Numbers 
            # |  Only calculate the sum of non repeating letters ,sum  Is the sum of all letters ,"abc"  and  "aaac" sum  The same is  7 
            return sum(1 << (ord(c) - ord('a')) for c in set(word))

        d, ans = defaultdict(int), 0
        for w in words:
            h = hashset(w)
            if d[h] < len(w):
                for other in d:
                    if not other & h:
                        ans = max(ans, d[other] * len(w))
                d[h] = len(w)
        return ans

389. Make a difference

Method 1 ： Count

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        d = {
    }
        for c in s:
            d[c] = d.get(c, 0) + 1
        for c in t:
            d[c] = d.get(c, 0) - 1 
            if d[c] < 0:
                
                return c

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        d = {
    }
        for c in s + t:
            d[c] = d.get(c, 0) + 1
        return [x for x in d if d[x]%2][-1]

Method 2 ： Sum up

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        return chr(sum(ord(c) for c in t) - sum(ord(c) for c in s))
        #  utilize  Counter ( Standard library  collections)
        # return list(Counter(t) - Counter(s))[0]

Method 3 ： An operation

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        res = 0
        for c in s + t:
            res ^= ord(c)
        
        return chr(res)

        # return chr(reduce(xor, map(ord, s + t)))

Method four ： Sort the list

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        s = list(s)
        t = list(t)
        s.sort()
        t.sort()
        for i in range(len(s)):
            if s[i] != t[i]:
                return t[i]
        return t[-1]

397. Integer substitution

Method 1 ： Memory search

class Solution:
    @cache #  Memory search 
    def integerReplacement(self, n: int) -> int:
        if n == 1: return 0
        if n & 1: #  Odd number   Add and subtract and divide by  2  There are two operations 
            return 2 + min(self.integerReplacement((n - 1) >> 1), self.integerReplacement((n + 1) >> 1))

        return 1 + self.integerReplacement(n >> 1)

Method 2 ： greedy

In recursive enumeration 「 Optimal solution 」 Is constant .

if n <= 3:return n - 1
 even numbers 
 Odd number  n % 4  Remainder is  1  or  3, Minus one or plus one  

class Solution:
    def integerReplacement(self, n: int) -> int:
        res = 0
        while n != 1:
            if n & 1:
                n += -1 if n & 2 == 0 or n == 3 else 1
            else:
                n >>= 1
            res += 1
        return res
        ##  recursive 
        # @lru_cache(None)
        def x(n):
            if n <= 3: return n - 1
            if n & 1 == 0: return 1 + x(n >> 1)
            if n & 4 == 1:
                return 3 + x((n - 1) >> 2)
            return 3 + x((n + 1) >> 2)
        return x(n)

405. Convert numbers to hexadecimal numbers

Method 1 ： An operation

The question requires that the given integer num Convert to hexadecimal number , Negative integers use complement operations .

In complement operation , The highest bit represents the sign bit , The sign bit is 0 Represents a positive integer and zero , The sign bit is 1 Represents a negative integer .32 The binary number of bit signed integers is 32 position , Because one hexadecimal number corresponds to four binary numbers , therefore 32 The hexadecimal number of a signed integer has 8 position . take num Binary numbers are divided into groups of four digits 8 Group , Convert each group into the corresponding hexadecimal number in turn , You can get num The hexadecimal number of .

Let's assume that binary numbers are 8 The group from low to high is the second 0 Group to No 7 Group , For the first i Group , Can pass (num >> (4×i)) & 0xf Get the value of this group , Its value range is 0 To 15（ That is, hexadecimal f）. The method of converting the values of each group into hexadecimal numbers is as follows ：

about 0 To 9, The number itself is a hexadecimal number ; about 10 To 15, Convert it to a To f Corresponding letter in .

For negative integers , Because the highest position must not be 0, Therefore, leading zeros will not appear . For zero and positive integers , Leading zeros may occur . Avoid leading zeros as follows ：
If num = 0, Then return directly 0;
If num > 0, When traversing each set of values , From the first not 0 The values of begin to be spliced into hexadecimal numbers .

Computer storage 32 Bit signed integer .int The storage range of type integer is $[-2^{31},2^{31}-1]$ Inside , And in the form of complement inside the computer , common 32 position , The highest bit is the sign bit , The negative sign bit is 1, A positive number is 0.

In the computer ,$[0,2^{31}-1]$ The hexadecimal storage method corresponding to the number in the range is 0x00000000-0x7FFFFFFF,（0 - 2147483647）,$[-2^{31},-1]$ The hexadecimal storage method corresponding to the number in the range is 0x80000000-0xFFFFFFFF$.（2147483648 - 4294967295）

You can add negative numbers together first $2^{32}$, Map it to $[2^{31},2^{32}-1]$ Within the scope of , You can directly carry out hexadecimal conversion .

Negative number plus 232 In fact, it is the complement of the absolute value of negative numbers 232 - abs(num)
It can also be calculated by and &, Or modular operation %, Unified positive and negative numbers .
num & 0xffffffff # remainder num % (2 ** 32 )

print(0xffffffff,2 ** 32 - 1) # 4294967295 4294967295

num & 0xffffffff This operation converts negative numbers to positive numbers , And the binary code of this positive number is exactly the same as 32 The binary encoding of negative numbers of bits is the same , But its operation is not as limited as the binary operation of negative numbers .

For convenience , We will advance the hexadecimal corresponding 16 Different characters are stored in the string s in , It is convenient to extract directly in the process of hexadecimal conversion .

Input is 0 when , Go straight back to “0” ;
When the input is a positive number , By constantly finding the remainder , Finally, flip the string to get the hexadecimal representation ;
When the input is negative , Using complement operation , Calculate the number after its complement operation , Process in positive steps , Finally, handle the sign bit , Be careful , When entering the minimum value of a negative number , The complement operation is 0 , And input is 0 Distinguish , Special treatment .

class Solution:
    def toHex(self, num: int) -> str:
        lib, ret = "0123456789abcdef", ""
        #  add  2**32  Negative complement  2**32 - abs(num)
        # 1 << 32 = 2 ** 32 = -1 & 0xffffffff + 1 = 4294967296
        # n = num + (1 << 32) if num < 0 else num 
        n = num & 0xffffffff #  remainder  num % (2 ** 32 - 1) 
        if n == 0: return "0"      

        while n:            
            # ret = lib[n % 16] + ret 
            # n //= 16

            ret = lib[n & 0xf] + ret #  Mask  0X0000000F -> 15
            n >>=  4  
            
        return ret

458. A Poor Pig

A particularly classic question ,1024 In a bucket , There is a poisonous , Ten mice can be tested , How to find the poisonous one at one time ?

take 0~1023 Written in binary , Ten at most , Every white mouse drinks all one for 1 Of （ One mouse, one ）
The final one to look for is the position of all dead mice 1, Other bits are 0

Ten white mice can try out 2^10 A barrel , What if it's twice ？
In fact, two times can be regarded as ternary , Each white mouse can try out one of them in two rounds 0 still 1 still 2
The first death is that one for 1, The second time is that time for 2, The one who didn't die was 0
In this way ,x The wheel should be converted into (x + 1) Base number , Want to find buckets stay x + 1 How many digits are under the base , That's the number of mice we need at least .

class Solution:
    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
        return ceil(log(buckets, minutesToTest//minutesToDie + 1))

476. The complement of numbers

Method 1 ： An operation

Find binary num The highest position is 1 Number of digits i, Then traverse num Of the $0\sim i$ Binary bits , Reverse them in turn . Masks can be constructed $mask=2^{i+1}-1$, take num And mask Xor operation .

class Solution:
    def findComplement(self, num: int) -> int:
        for i in range(1, 30 + 1): 
            if num < (1 << i): break
        else: i = 31
        # i - 1  yes  num  The highest bit in the binary bit is  1  Number of digits 

        mask = (1 << i) - 1
        return num ^ mask

Then how to get and num Binary of the same length 1 Well ？

1. Find the front one by position 1;
2. utilize -1 The complement of is all 1 Of （~0 It's fine too ）. And then according to mask And num Meet each other , Judge mask Whether the right shift of is in place , If there is a coincidence , Then the phase and result will not be equal to zero ！

class Solution {
    
    public int findComplement(int num) {
    
        mask = -1 # 0xFFFFFFFF  It's all about  1  Complement code 
        while (mask & num) > 0:
            mask <<= 1
        
        return ~mask ^ num

The finger of the sword Offer II 003. front n A number in binary 1 The number of

class Solution {
    
    public int[] countBits(int n) {
    
        int[] ans = new int[n + 1];
        int highBit = 0;
        for(int i = 1; i < n + 1; i++) {
    
            // ans[i] = Integer.bitCount(i);
            // ans[i] = bit1(i);
            // ans[i] = bit2(i);
            ans[i] = ans[i & (i - 1)] + 1;
            // ans[i] = ans[i >> 1] + (i & 1); //  Its lowest  1, Shift right to divide parity .
            //  Record  i  The highest  bit  position . highest  1
            // if ((i & (i - 1)) == 0) highBit = i; 
            // ans[i] = ans[i - highBit] + 1;
        }
        return ans;
    }

    int bit1(int x){
    
        int res = 0;
        while(x > 0){
    
            res += x % 2; x /= 2;
        }
        return res;
    }
    
    int bit2(int x){
    
        int res = 0;
        while(x > 0){
    
            x &= x - 1; res++;
        }
        return res;
    }
}

89. Gray code

class Solution {
    
    public List<Integer> grayCode(int n) {
    
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < 1 << n; ++i)
            res.add(i ^ i >> 1);
        return res;
    }
}

10、 338. Bit count
11、 342. 4 The power of
12、371. Sum of two integers

17、 461. Hamming distance
18、 476. The complement of numbers
19、 477. The sum of Hamming distances
20、 526. A beautiful arrangement
21、 1178. Guess the riddle
22、 1711. Big meal count
23、 The finger of the sword Offer 15. Binary 1 The number of