# Bit Mainpulatoin [Binary Number with Alternating Bits](https://leetcode.com/problems/binary-number-with-alternating-bits/description/) Reverse Bits * Setting a bit `num |= 1 << x;` * clearing a bit `num &= ~(1<> x) & 1` * **1 << i 就是Math.pow(2, i)** * **`n & (-n)`get the least significant standing bit,就是找最右边的1所代表的数，比如n = 6(110), n & (-n) = 2(10)** * **`n & (n - 1)` 效果为减去 n 的二进制表示中最右边为 1 的 bit,等效为`n - n & (-n)`,n =6, n &(n-1) = 4** * **`n &(n - 1) == 0`的话就说明n is power of 2** * **`n + (n & -n)` 就是直接在最低位的 1 上做进位加法** * **如果是Unsigned Bit, 判断终止条件不能写`n > 0`,而应该是`N != 0`，**[**参见Number of 1 Bits**](https://leetcode.com/problems/number-of-1-bits/) * a^0 = a * a^a = 0 * 0b001100 ^0b101010 = 0b100110 * **所以可以in place swap(a, b)** ``` a ^= b; b ^= a; a ^= b; ``` * Reverse Bits * Counting Bits ## [Number of 1 Bits](https://leetcode.com/problems/number-of-1-bits/) * 这题关键在于是Unsigned Bit,所以在while loop里的条件不能写n > 0,而应该是N != 0 * Naive的想法就是找这32 bits里有多少个1,可以用`1 << i`的技巧，这个方法有个好处就是可以算上最高位的1，不用care是否是Unsigned Bit ``` // you need to treat n as an unsigned value public int hammingWeight(int n) { int cnt = 0; //naive way using bit shift for(int i = 0; i < 32; i++){ if((n & (1 << i)) != 0){ cnt++; } } return cnt; } ``` * 还有一种就是用n -= n & (-n)的方法，或者n = n & (n - 1)。但是要注意是`while(n != 0)` ``` // you need to treat n as an unsigned value public int hammingWeight(int n) { int cnt = 0; //cannot be while(n > 0) while(n != 0){ n-= n & (-n); cnt++; } return cnt; } ``` ## Reverse Bits * 拿到没做过的题目先想Brute Force,很多时候思路不见得不对 * 先shift bit,再赋值 ``` // you need treat n as an unsigned value public int reverseBits(int n) { int reverse = 0; for(int i = 0; i < 32; i++){ reverse = reverse << 1;//shift to the left bit if((n & 1 << i) != 0){ reverse += 1; } } return reverse; } ``` * **FOLLOW UP: 如果多次call method如何优化？** * We can divide an int into 4 bytes, and reverse each byte then combine into an int. * For each byte, we can use cache to improve performance. ## [Counting Bits](https://leetcode.com/problems/counting-bits/) * 给一个数num,要求返回0 <= i <= num的所有i包含bit 1的个数 * 这题可以用Fenwick Tree的思路做 * 当前数为i（假设是1010）, 先找到i&(i - 1)的bit of 1的个数count\[i&(i - 1)],可以发现count\[i] = count\[i&(i - 1)] + 1 * 这个想法真的很巧妙 ``` public int[] countBits(int num) { int[] count = new int[num + 1]; for(int i = 1; i <= num; i++){ count[i] = count[i & (i - 1)] + 1; } return count; } ``` ## [Flip Bit](https://www.lintcode.com/en/problem/flip-bits/) * given two numbers A and B, check how many different bits * 一开始想到的是把32位都循环一遍，然后check最后一位，如果两个数的最后一位不一样就cnt++ ``` public static int bitSwapRequired(int a, int b) { // write your code here int cnt = 0; for (int i = 0; i < 32; i++) { int first = a & 1; int second = b & 1; if (first != second) { cnt++; } a >>= 1; b >>= 1; } return cnt; } ``` * 上面这个方法虽然也过了，但显然没有get point * 这题的核心其实是看C= A^B, get the number of bit 1 in C ``` public static int bitSwapRequired(int a, int b) { // write your code here int cnt = 0; for (int c = a ^ b; c != 0; c &= c - 1) { cnt++; } return cnt; } ``` ## Single number * 每个数出现两次except for one, find that single one * XOR, a^a = 0 ``` public int singleNumber(int[] nums) { int res = 0; for (int num : nums) res ^= num; return res; } ``` ## [Single Numebr II](https://leetcode.com/problems/single-number-ii/) * 3 \*n + 1个数，每个数出现3次except for one num,find it * 把32 bits的每个bit位上求和sum, 如果sum % 3 != 0, 则说明res在此bit x上为 1 ``` public int singleNumber(int[] nums) { //every int number can be seen as a 32-bit number //so we can count for each bit //if sum of each bit mod 3 != 0, it means this bit is one of bit of the single numebr if(nums == null || nums.length == 0) return -1; int res = 0; for(int i = 0; i< 32; i++) { int sum = 0; int x = 1 << i; for(int j = 0; j < nums.length; j++) { if((x & nums[j]) != 0) sum++; } if(sum % 3 != 0) res |= x; } return res; } ``` ## [Single Number III](https://leetcode.com/problems/single-number-iii/) * 有两个数只出现一次，其余都出现2次 * 1 5 2 2 3 3 4 4 * if XOR all nums. the res should be a^b, res != 0 * 二进制的某一位是1 * 意味着a和b在某一位上是不一样的 * diff &= -diff;//get the right most "1" bit * 把所有num分成两拨，一拨是第k位为0，另一拨是第k位为1 * 然后各自一拨single number I ``` if(nums == null | nums.length == 0) return null; int[] res = new int[2]; int diff = 0; for(int num : nums) diff ^= num; diff &= -diff;//get the right most "1" bit , if diff = 6(110), diff &(-diff) = 2(010) for(int num : nums) { if((diff & num) == 0) { res[0] ^= num; }else res[1] ^= num; } return res; ``` ## Hamming Distance ``` public int hammingDistance(int x, int y) { int cnt = 0; int xor = x ^ y; while (xor != 0) { if (xor % 2 == 1) { cnt++; } xor >>= 1; } return cnt; } ``` ## Power of Two * 利用n & (n-1) == 0性质 ``` public boolean isPowerOfTwo(int n) { if (n <= 0) return false; return (n & (n - 1)) == 0; } ``` ## Power of Three * 没法用bit manipulation ``` public boolean isPowerOfThree(int n) { if (n <= 0) return false; while (n > 1) { if (n % 3 != 0) return false; n /= 3; } return n == 1; } ``` ## Power of Four * 这题naive solution就是check num %4 == 0, num /=4, Time: O(logN) * 还可以用bit manipulation, count bit i = i+2, num = 1 << i; Time: O(32) ``` class Solution { /* 1. naive %4 solution, O(LogN) 2. count bit i = i+2, num = 1 << i; O(32) */ public boolean isPowerOfFour(int num) { for (int i = 0; i < 32; i += 2) { if (num == 1 << i) return true; } return false; } // public boolean isPowerOfFour(int num) { // if (num <= 0) return false; // while (num > 1) { // if (num % 4 != 0) return false; // num /= 4; // } // return true; // } } ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://syjohnson11.gitbook.io/leetcode/9_math/bit_shift_a__1.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.