Bitwise Operation

Union-find applications: Percolation Problem discriptions Percolation data type. To model a percolation system, create a data type Percolation with the following API: public class Percolation { public Percolation(int n); // create n-by-n grid, with all sites blocked public void open(int row, int col); // open site (row, col) if it is not open already public boolean isOpen(int row, int col); // is site (row, col) open? public boolean isFull(int row, int col); // is site (row, col) full? public int numberOfOpenSites(); // number of open sites public boolean percolates(); // does the system percolate? } Monte Carlo simulation. To estimate the percolation threshold, consider the following computational experiment: ...

如何实现快速的幂运算？ 要求$c = a^b$, 按照朴素算法把a连乘b次的时间复杂度是$O(n)$. 而快速幂能做到$O(\log n)$。把b转换为二进制, 二进制数第i位的权为$2^{i-1}$，就可以把二进制拆分为若干个以2为底的真数, 然后利用幂数的性质，例如用朴素算法求$a^{11}$要求乘11次. 考虑到11的二进制为1011, 如果把$a^{11}$拆分为: $$a^{11} = a^{a_0 2^0 + a_1 2^1 + a_2 2^2 + a_3 2^3} = a^1 a^2 a^8$$ 可以看到每一个因子都是上一个因子的平方，利用$a^2 a^2$求出$a^4$, 同样利用$a^4$的平方求出$a^8$, 每次计算只需要用到上一次计算出来的结果, 所以总的运算次数是4次. 任何一个数b最多能写成长度为$O(\log b)$的二进制, 因此这个算法就是$O(\log n)$. 在程序设计中是根据b的二进制中是否为1来控制是否乘以上一次翻倍的积 不断右移b, 直到b不再有1： 根据当前位的权重（当前b最后一位）是否为1来决定c是否乘以最新的a 把a平方，用于下一位计算 在Java中要考虑极端值INT_MIN // 递归 public double myPow(double x, int n) { if(n==0) return 1; double temp = myPow(x, n/2); if (n % 2 ==0) return temp * temp; else { if(n > 0) return x*temp*temp; else return (temp*temp) / x; } } // 循环 public double myPow(double x, int n) { double ans = 1; if(n < 0){ n = -(n+1); // 处理极端值 x = 1/x; ans *= x; } System.out.println(n); while (n > 0) { if ((n & 1) == 1) ans *= x; x *= x; n >>= 1; } return ans; } 快速幂取余 求a^b mod c. 如果b是偶数, a^b mod c = $(a^2)^{b/2} \% c$ 如果b是奇数, a^b mod c = $((a^2)^{b/2} \times a) \% c$ ...

“找出只出现一次的数”， “找出唯二的只出现M次的数”， “找出缺失的数”等等这类问题，都可以利用异或操作的特性， 即一个整数和自己进行异或运算会归0的性质。 找出缺失的数字 问题1：给定一个包含n个不同数字的数组，取自0,1,2,...,n，找到数组中缺少的数字。 最直觉的解法是利用等差数列的性质直接数学求解。但这个方法限制于等差数列. 问题2: 在一个长度为n的数组里的所有数字都在0 ~ n-1之间, 数组中有些数字是重复的, 找出任意一个重复的数字. 这也是«剑指offer»的一道题. 但是如果利用数组大小和元素范围的特性, 就可以发现, 这里的数组的大小和数字的范围是有限定关系的. 对于第二个问题, 假如没有重复, 那么重新排列的话数组每一个位置都可以放上自己对应的数字. 对于第一个问题, 假如没有缺失, 那么除了每一个index都可以重新放上自己对应的数字外, 还会多出一个最大的数字没地方放. 这样就可以把数组包含的数字解读为index, 然后在遍历检查数组时, 同时检查以各个数字为index的其他位置的数字. 使用这种思路可以同时解决两个问题, 这里以问题1解法为例: public int missingNumber(int[] nums) { int n = nums.length; int misP = n; // points to the position where misssing. for (int i = 0; i < n; i++) { while (i != nums[i] && nums[i] != misP) { int j = nums[i]; nums[i] = nums[j]; nums[j] = j; } if (nums[i] == misP) misP = i; } return misP; } 找出只出现一次的数 问题3：在一个非空整数数组，找出那个只出现了一次的元素，已知其余每个元素均出现两次。 ...

求两个整数的汉明距离 hamming distance Leetcode 461 两个整数之间的汉明距离是该两个数之间不同的位数。 给定两个整数x和y，计算汉明距离。问题也可以理解为对于两个整数m和n, 需要改变m的二进制多少位才能得到n: /** Use Brian Kernighan's way to count bits */ public int hammingDistance(int x, int y) { x = x ^ y; y = 0; while(x != 0){ y++; x &= x - 1; } return y; } public class Solution { public int hammingDistance(int x, int y) { return Integer.bitCount(x ^ y); } } 同样用到Brian Kernighan算法： ...

不使用加减符号求和整数 不能使用+和-, 仅通过^和&操作来求和两个整数a. 参考 每位相加可能会产生进位(carry), 所以可以把相加拆分为两部分, 如759 + 674可以拆分为不考虑进位的部分323和仅考虑进位的部分1110, 故759 + 674 = 323 + 1110 = 1433. 二进制的加法也是从低位开始逐步往高位计算: 进行一位二进制的加法, 也就是暂不考虑进位的位相加: 0+0=0， 0+1=1, 1+0=1， 1+1=0, 那么就是^操作. 所得的和作为新的a. 求进位: 通过a & b判断是否进位, 因为只有两个位均为1才会进位. 所得的进位左移一位作为新的b. 不断重复这个过程, 把低位的进位传递到高位, 累加到a中, 直到进位为0, 最后得到的a就是答案. public class Solution { public int getSum(int a, int b) { while (b != 0) { // 关键在于判断终止的时机 int c = a & b; //carry a ^= b; //add b = c << 1; } return a; } } 涉及的运算就是一个多位二进制加法真值表：(对应于硬件中的全加器) ...

通过位移实现很多风骚的操作， 参考这个视频。 检查一个数是否是偶数, 本质上就是取最后一位来判断, 如果是1那么就一定是奇数, 反之则为偶数: (x & 1) == 0 Check if power of two: (x & x - 1) == 0 因为如果数x是以2底的真数, 那么其二进制一定只有一个位置是1, 如0b1000, 那么x-1就会变成只有该位置是0其右边所有位变为1, 即0b0111, 也就是说这种情况下x和x-1所有位置都互异. 那么它们的位与运算就是x & x - 1 = 0b0000. x & x - 1的广义用途是求x二进制中1的个数, Counting bits set: unsigned int v; // count the number of bits set in v unsigned int c; // c accumulates the total bits set in v for (c = 0; v; c++) { v &= v - 1; // clear the least significant bit set } Brian Kernighan’s algorithm takes O(log N) to count set bits (1s) in an integer: each iteration sets the least significance bit that isn’t zero to zero - and only it. Since each iteration converts exactly bit from 1 to 0, it’ll take as many iterations as there are non-0 bits to convert all the bits to 0(and thus v == 0 and the loop finishes). An integer n has log(n) bits, hence the worst case is O(log(n)) ...

一些常规的操作， 参考这个视频。 基本位操作 把某一位变为1： def set_bit(x, position): mask = 1 << position return x | mask bin(set_bit(0b110, 0b101)) 输出0b100110. 因为x = 0b110 = 6, 翻转第五位，就用position = 0b101 = 5， 得到mask = 0b00100000, 用|把第五位变为1. 清除某一位（1变0)： def clear_bit(x, position): mask = 1 << position return x & ~mask 通过XOR^和1来翻转某一位： def flip_bit(x, position): mask = 1 << position return x ^ mask 通过&1可以作为取位操作, 来判断某一位是否是1: def is_bit_set(x, position): shifted = x >> position return shifted & 1 0b1100110 >> 0b101 = 0b11, 0b11 & 0b01 = 1 根据参数state来控制修改某一位, 如果参数是1那么就是set, 如果是0那么就是clear: def modify_bit(x, position, state): mask = 1 << position return (x & ~mask) | (-state & mask) 如果state = 0b1, -state = 0b11111111 如果state = 0b0, -state = 0b0

在很多语言中，字符char类型是八位, 那么可能取值有256种(-128 ~ -1, 0 ~ 127). 但是用二进制表示为0000 0000 ~ 1111 1111, 无符号整数的全部位都表示数值，而有符号数的最高位是符号位（0表示正数，1表示负数），所以实际表达数值的只剩下n-1位。这样理论上char的取值应该是1111 1111 = -127到0111 1111 = 127. 而-128 = 1 1000 0000需要9位来表达, 所以char是如何仅仅通过八位表达-128? 首先, 因为计算机只能做加法, 所以减法操作要转化为加法, 尝试将符号位参与运算, 1-1就转化为1 + (-1), 用二进制表达为0000 0001 + 1000 0001 = -2, 很明显是错的. 如果用原码表示, 让符号位也参与计算, 显然对于减法来说, 结果是不正确的. 这也就是为何计算机内部不使用原码表示一个数. 为了避免这种错误, 引入反码(正数的反码是其本身, 负数的反码是符号位不变, 其余位取反), 用-1的原码1000 0001的反码1111 1110来表达-1, 这样1 + (-1) = [0000 0001]反 + [1111 1110]反 = [1111 1111]反, 转为原码1000 0000 = -0. 发现用反码计算减法, 结果的真值部分是正确的. ...