Math / Bit Operation
Math
TODO Arithmetic
Divide two integers without using multiplication, division, and mod
Big Integer
Power
Exercises
TODO Counting digits
Bit Manipulation
Population count (counting bits of 1)
Population Count for One Number
- Solution: For every x, perform x&(x-1) sets the lowest bit of 1 to 0. Thus, we keep doing this until the number reaches zero, and the times we perform this operation is the count.
Population Count for 0 to N
- Solution: We can formulate the previous operation as count[i] = count[i&(i-1)] + 1. Thus we can calculate the counts for 0 to N using dynamic programming.
- Solution: We can also do not use this trick, and use a more intuitive relation: count[i] = count[i>>1] + (i&1)
Other applications
- Tell if a number if power of two: wheter x&(x-1) == 0
Exercise
Bitwise XOR
Overview
- Bitwise XOR between two numbser of two useful features
- A number XOR it self results in 0: x^x = 0
- A number XOR 0 results in the number it self: x^0 = x
- We can use these two features to solve some problems
Find the missing number in a range
- Description: Given an array containing n distinct number from range [0,n]
Return the only number in the range that is missing from the array
- Solution: Given that a number XOR with itself will always result in 0, and that XOR is both communicative and associative, we can XOR all the numbers from the array, as well all the numbers from the range. All the numbers that is both in the array and in the range will be zero out, leaving the only number that is missing from the array.
- Solution: Cyclic Sort
Find the single number when other numbers appear twice
- Description: Given a non-empty array of integers nums, in which every element appears twice except for one. Find that single one.
- Solution: We follow the same bitwise XOR approach. Numbers that appear twice will zero out, resulting in the single number.
- Time complexity: O(n), Space complexity: O(1)
Find the single number when other numbers appear three times
- Description: Given a non-empty array of integers nums, in which every element appears thrice except for one. Find that single one.
- Solution: This time the other numbers all appear three times, so XOR cannot eliminate them. However, we can actually think of XOR as performing bitwise addition and MOD 2. Therefore, for this case, we can perform bitwise addtion and MOD 3.
Find the two single number when other numbers appear twice
- Description: Given a non-empty array of integers nums, in which every element appears twice except for two. Find that two numbers that appear once.
- Solution: Bitwise XOR: Follow the same approach as in “Single Number’, we end up by getting the two single numbers’ XOR. Since the two numbers are distinct, their XOR result must has at least one bit that is one, then we can use this bit to divide all the numbers in the array into 2 groups, each containing one of the two single numbers. Then we apply the XOR approach to each group, and each will result in one of the two single numbers
Exercise