作者:小傅哥 博客:https://bugstack.cn
❝沉淀、分享、成长,让自己和他人都能有所收获!😜 ❞
你是什么时候注意到位运算?
从毕业入职公司看大佬的代码出现 2 << 4
开始?从小白晋升高开读框架的源码看到 MAXIMUM_CAPACITY = 1 << 30;
开始?还是从什么时候开始?
其实二进制的位运算一直在我们那身边,从你开始编写 Hello Word 打印输出时就有二进制流的处理,只不过隐藏的很深不好发现。所以在我们开始意识到代码和二进制的关系往往都是来自于看到可以用二进制完成的计算,包括;二进制计算效率高于乘机,也包括二进制可以更好的体现出你要设置值的大小范围。比如你要设定一个指定范围大小的 Int 值 = 1073741824,那么是给这样一个整数值看起来直观,还是二进制 1<< 30 更直观呢?其实他们两个值是相等的。所以这样的情况下也会有二进制运算的体现。
而小傅哥在学习编程阶段,第一次注意到二进制的运算是关于a、b两个值的互换,如果不引入第三个值就可以完成?
int a = 2, b = 3;
a = a ^ b;
b = a ^ b;
a = a ^ b;
一个 ^ 帽子一样的运算符,就把两个数给替换,替换后 a = 3,b = 2 那它是怎么办到的呢?
^ 异或运算:两个操作数的同位中,如果值相同(都是 0 或者都是 1)则为 0,不同(一个是 0,一个是 1)则为 1
而二进制的运算魅力还远不至于此,还可以完成奇偶判断、有效位计算、乘法、加法等。这些内容的学习可以让我们研发人员,积累编程逻辑和拓展思维模式。接下来小傅哥就带着大家学习一下。
位操作是程序设计中对位数组或二进制数的一元和二元操作。在许多古老的微处理器上,位运算比加减运算略快,通常位运算比乘除法运算要快很多。在现代架构中,位运算的运算速度通常与加法运算相同(仍然快于乘法运算),但是通常功耗较小,因为资源使用减少。
四种基本的位运算包括;与&、或|、非~、异或^
int a = 1; // 0001
int b = 2; // 0010
int c = 4; // 0100
int d = 8; // 1000
int e = 15;// 1111
// 与运算;0001
System.out.println(Integer.toBinaryString(a & e)); // 0001
// 或运算;0011
System.out.println(Integer.toBinaryString(a | b)); // 0011
// 非运算;0101
System.out.println(Integer.toBinaryString(a ^ c)); // 0101
// 异或运算;...11110111
System.out.println(Integer.toBinaryString(~d));
public int getBit(int number, int bitPosition) {
return (number >> bitPosition) & 1;
}
public int setBit(int number, int bitPosition) {
return number | (1 << bitPosition);
}
public int clearBit(int number, int bitPosition) {
int mask = ~(1 << bitPosition);
return number & mask;
}
设置位值
,把1左移指定位数后取反,从 0010 得到 1101 并与目标值 number 做与&运算,清掉目标位的值。public int updateBit(int number, int bitPosition, int bitValue) {
int clearMask = ~(1 << bitPosition);
return (number & clearMask) | (bitValue << bitPosition);
}
public boolean isEven(int number) {
return (number & 1) == 0;
}
public boolean isPositive(int number) {
if (number == 0) {
return false;
}
return ((number >> 31) & 1) == 0;
}
public int multiplyByTwo(int number) {
return number << 1;
}
public int divideByTwo(int number) {
return number >> 1;
}
public int switchSign(int number) {
return ~number + 1;
}
public int multiply(int a, int b) {
int multiply = 0;
while (a != 0 && b != 0) {
System.out.print("计算步骤(" + (isEven(b) ? "偶数" : "奇数") + "):a(" + String.format("%04d", Integer.valueOf(Integer.toBinaryString(a))) + ") = " + a + " | b(" + String.format("%04d", Integer.valueOf(Integer.toBinaryString(b))) + ") = " + b);
// b 是偶数:2a * (b/2)
if (isEven(b)) {
a = multiplyByTwo(a);
b = divideByTwo(b);
}
// b 奇数
else {
// b 正数:2a * (b - 1)/2 + a
if (isPositive(b)) {
multiply += a;
a = multiplyByTwo(a);
b = divideByTwo(b - 1);
}
// b 负数:2a * (b + 1)/2 - a
else {
multiply -= a;
a = multiplyByTwo(a);
b = divideByTwo(b + 1);
}
}
System.out.println(" | multiply(" + String.format("%04d", Integer.valueOf(Integer.toBinaryString(multiply))) + ") = " + multiply);
}
return multiply;
}
public int multiplyUnsigned(int number1, int number2) {
int result = 0;
int multiplier = number2;
int bitIdx = 0;
while (multiplier != 0) {
if ((multiplier & 1) == 1) {
System.out.println(number1 + " << " + bitIdx + " = " + (number1 << bitIdx));
result += number1 << bitIdx;
}
bitIdx += 1;
multiplier = multiplier >> 1;
}
return result;
}
目的:计算无符号二进制乘积
公式:
= 16 + 8 + 2
= 26
逻辑:每个数字都可以表示成一系列2的幂之和。例如 13 的二进制是 1101,最右侧第1位1,是2的0次幂,所以对应2的进制值是左移0位。再比如13的右数第3位是1,对应位置值是4也就是2的2次幂,所以对应2的进制值是左移2位。最终把这些值相加就是乘积值。
public int countSetBits(int originalNumber) {
int setBitsCount = 0;
int number = originalNumber;
while (number != 0) {
setBitsCount += number & 1;
number >>>= 1;
}
return setBitsCount;
}
public int bitsDiff(int number1, int number2) {
return countSetBits(number1 ^ number2);
}
public int bitLength(int number) {
int bitsCounter = 0;
while ((1 << bitsCounter) <= number) {
bitsCounter += 1;
}
return bitsCounter;
}
public boolean isPowerOfTwo(int number) {
return (number & (number - 1)) == 0;
}
public int fullAdder(int a, int b) {
int result = 0;
// 计算每次的进位值,1 + 1 = 0010 进位为1。是一种&运算。
int carryOut = 0;
System.out.println("| aBit | bBit | carryIn | aiPlusBi | bitSum | carryOut | result |");
for (int i = 0; i < 32; i++) {
int aBit = getBit(a, i);
int bBit = getBit(b, i);
int carryIn = carryOut;
System.out.print("| " + aBit + " | " + bBit + " | " + carryIn);
// 加和 - 两个值;如果相同则为0,不相同则为1
int aiPlusBi = aBit ^ bBit;
System.out.print(" | " + aiPlusBi);
// 加和 - 进位;
int bitSum = aiPlusBi ^ carryIn;
System.out.print(" | " + bitSum);
// 进位;同位置 ai & bi = 1 | 与进位 aiPlusBi & carryIn = 1
carryOut = (aBit & bBit) | (aiPlusBi & carryIn);
System.out.print(" | " + carryOut + "(" + Integer.toBinaryString(carryOut) + ") ");
// 累加;把当前位置计算的值,左移n位
result = result | (bitSum << i);
System.out.println(" | " + result + "(" + String.format("%04d", Integer.valueOf(Integer.toBinaryString(result))) + ")|");
}
return result;
}
- END -
你好,我是小傅哥。一线互联网java
工程师、T8架构师,开发过交易&营销、写过运营&活动、设计过中间件也倒腾过中继器、IO板卡。不只是写Java语言,也搞过C#、PHP,是一个技术活跃的折腾者。