1、特殊数字的16进制与二级制对应关系
- 0xaaaaaaaa = 10101010101010101010101010101010(偶数位为1,奇数位为0)
- 0x55555555 = 1010101010101010101010101010101 (偶数位为0,奇数位为1)
- 0x33333333 = 110011001100110011001100110011 (1和0每隔两位交替出现)
- 0xcccccccc = 11001100110011001100110011001100 (0和1每隔两位交替出现)
- 0x0f0f0f0f = 00001111000011110000111100001111 (1和0每隔四位交替出现)
- 0xf0f0f0f0 = 11110000111100001111000011110000 (0和1每隔四位交替出现)
利用上述具有特殊二进制的整数,可以很方便进行位操作,而且该整数的十六进制形式比较好记,也不用写那么多的0,1。
2、二进制运算
2.1 求余运算
取余操作中如果除数是2的幂次方则等价于其除数减一的与操作 也就是说hash % length == hash & (length - 1)的前提是length 是 2的n次方,并且采用二进制位操作&,相对于%能够提高运算效率,这就解释了hashmap的长度为什么是2的幂次方。
- 普通的求余运算为: n % m,优化之后为n & (m - 1)。
/**
* 求模运算
* 求一个数n模m的值,也就是求n除以m之后的余数,这里m为2的幂次方。
* 普通的求余运算为: n % m
* 优化之后为: n & (m - 1)
*
* @param n 被除数
* @param m 除数
* @return
*/
public static int getMod(int n, int m) {
return n & (m-1);
}
2.2 计算给定数字的二进制表示中1出现的个数
Count the number of ones in the binary representation of the given number(计算给定数字的二进制表示中1出现的个数)。
算法1: 每次n&(n-1)操作都是将n最末尾的1反转为0,因此反转个数即为1的个数
public static int count_one(int n) {
int count = 0;
while (n > 0) {
// n&(n-1)作用是消除最低位的1,如二级制 111010&111001=111000
n = n & (n - 1);
count++;
}
return count;
}
算法2: 给定数字与1按位与,如果数字的最后一位为1,则结果为1,每次计算后将数字右移一位,循环计算,直到数字为0。
public static int count_one2(int n) {
int count = 0;
while (n > 0) {
if ((n & 1) == 1) {
count++;
}
n >>= 1;
}
return count;
}
算法3: java API中的Integer.bitCount,将相邻位的1相加,存储1的个数,五次就可以加完整个32位数.以下是源码。
public static int bitCount(int i) {
// HD, Figure 5-2
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
2.3 将数字n的第bit位 置1
public static int resetBit_1(int n, int bit) {
return n |= 1 << bit;
}
2.4 将数字n的第bit位 置0
public static int resetBit_0(int n, int bit) {
return n &= ~(1 << bit);
}
2.5 数字n的第bit位是否为0
public static boolean isBit0(int n, int bit) {
return (n & (1 << bit)) != 0;
}
2.6 删除从右边起第一个为1的bit(将该位的1置为0)
public static int resetLowBit1To0(int n) {
return n & (n - 1);
}
2.7 判断一个数是否是2的幂次方
判断一个数是否是2的幂次方,这个数用二进制数表示时,只有一位为1
public static boolean isPower(int n) {
if ((n & (n - 1)) == 0)
return true;
else
return false;
}
2.8 判断一个数是否是4的幂次方
判断一个数是否是4的幂次方。这个数用二进制数表示时,只有一位为1并且只可能出现在偶数位置。
/**
* 判断一个数是否是4的幂次方 这个数用二进制数表示时,只有一位为1并且只可能出现在偶数位置
*
* 0x55555555是16进制,2进制是1010101010101010101010101010101
*
* 式子左边的是判断n是否为2的幂次方,因为4的幂次方一定是2的幂次方,如果2的幂次方都不是,
* 那就一定不是2的四次方了。第二个条件就是0x55555555,5的二进制位0101,又因为该数与n进行与运算,
* 因此,也就是奇数位全部为与0进行与——置0,偶数位全部与1进行与——保留原本比特位。
*
* @param n
* @return
*/
public static boolean isPowerOfFour(int n) {
return ((n & (n - 1)) == 0) && ((n & 0x55555555) != 0);
}
2.9 计算2个数的和,递归方法
public static int getSum(int a, int b) {
return b == 0 ? a : getSum(a ^ b, (a & b) << 1);
}
2.10 计算2个数的差,递归方法
public static int getSubstract(int a, int b) {
return b == 0 ? a : getSubstract(a ^ b, (~a & b) << 1);
}
2.11 计算2个数的和,循环方法
让我们以2+3为例来看一下: 0010(2),0011(3),首先看最右边的第一位,0+1为1,不进位,接着1+1=2,要进位。我们如何判断相加的两个bit只有一个1?答案是使用异或操作。 我们如何判断相加的两个bit为两个1?答案是使用与操作。因此 a&b的结果使得所有该进位的位置为1,a^b的结果使得所有该进位的位置0,不该进位的位置为其应该有的数。在进行初步的计算之后,我们需要把该进位的位置加上,因此进位之后,是在其前面的bit位加1,因此,需要将b左移1位,然后与初步计算结果相加,也就是我们递归方法的核心。
- 说说为什么最后b会变成0: 首先,carry <<1一定会使得carry中多一个0,因为左移之后最右边的位置一定为0,但是其前面可能舍弃了一个1,因此carry<<1使得carry的bit位的0的个数逐渐增加。其次,carry = a & b 这个使得b中的0得以保存,因为0 & 任何数都为0 因此,这两个条件使得最后b一定为0.同理,两个数相减也是一样的道理。首先a^b得到bit位上位数相同的位置全部为0,不同的位置为1,因为0-0=0,1-1=0;其次,a&b得到需要借位的bit位,因此只有0-1需要借位,1-0不需要借位,因此a & b刚好符合。
public static int getSum(int a, int b) {
if (a == 0) {
return b;
}
if (b == 0) {
return a;
}
int carry = 0;
while (b != 0) {
// If both bits are 1, we set the bit to the left (<<1) to 1 -- this is the
// carry step
carry = (a & b) << 1;
// If both bits are 1, this will give us 0 (we will have a carry from the step
// above)
// If only 1 bit is 1, this will give us 1 (there is nothing to carry)
a = a ^ b;
b = carry;
}
return a;
}
2.12 找到丢失的数字,与相同的数异或两次后为0
一个正常数组包括0,1,2,3,4,5…n-1,但是现在这个数组中少了一个数,求这个数是多少?例如:[0,1,3]输出结果为2。
public static int missingNumber(int[] nums) {
int ret = 0;
for (int i = 0; i < nums.length; ++i) {
ret ^= i;
ret ^= nums[i];
}
return ret ^= nums.length;
}
2.13 找到最高的一位数
public static int higestOneBit(int i) {
i |= i >> 1;
i |= i >> 2;
i |= i >> 4;
i |= i >> 8;
i |= i >> 16;
return (i + 1) >> 1;
}
2.14 反转二进制位
/**
* 反转二进制位 翻转的顺序表示:abcdefgh -> efghabcd -> ghefcdab -> hgfedcba
*
* @param n
* @return
*/
public static int reverseBit(int n) {
n = (n >> 16) | (n << 16);
n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
return n;
}
/**
* 反转二进制位
*
* 该解法的主要思路是:一个32位的mask,并且其32位中只有一个位为1,开始时,使其置1位位于最左端,
* 并依次向最右移动,同时,从最右端开始检测n,如果n的对应位为1,则将结果或上mask。
*
* @param n
* @return
*/
public static int reverseBits(int n) {
int mask = 1 << 31, res = 0;
for (int i = 0; i < 32; ++i) {
if ((n & 1) != 0)
res |= mask;
mask >>= 1;
n >>= 1;
}
return res;
}
2.15 找到从右边起,第一个为1的位,其余位置0
找到从右边起,第一个为1的位,其余位置0(注:主要利用补码 = 反码 + 1)
public static int getFirstOneFromRight(int n) {
return n &= (-n);
}
2.16 范围[m,n]之间所有数字与的结果
多个数字相与,只要其中有一个数字为0,结果就是0,而且,我们知道在数字递增的过程中,低位的数字总是在不断地变化,因此,我们只需要找到m与n相同的高位数字就行。例如,5,6,7的二进制分别为:101 110 111,全部一样的部分为第三位,都为1,因此最后输出的结果为4。
public static int rangeBitwiseAnd(int m, int n) {
int i = 0;
while (m != n) {
m >>= 1;
n >>= 1;
++i;
}
return (m << i);
}
评论区