侧边栏壁纸
博主头像
孔子说JAVA博主等级

成功只是一只沦落在鸡窝里的鹰,成功永远属于自信且有毅力的人!

  • 累计撰写 292 篇文章
  • 累计创建 132 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

算法:常见的位操作bit manipulation

孔子说JAVA
2019-10-17 / 0 评论 / 0 点赞 / 88 阅读 / 4,943 字 / 正在检测是否收录...

1、特殊数字的16进制与二级制对应关系

  1. 0xaaaaaaaa = 10101010101010101010101010101010(偶数位为1,奇数位为0)
  2. 0x55555555 = 1010101010101010101010101010101 (偶数位为0,奇数位为1)
  3. 0x33333333 = 110011001100110011001100110011 (1和0每隔两位交替出现)
  4. 0xcccccccc  = 11001100110011001100110011001100 (0和1每隔两位交替出现)
  5. 0x0f0f0f0f    = 00001111000011110000111100001111 (1和0每隔四位交替出现)
  6. 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);
}
0

评论区