位运算

位运算相加

二进制相加可以用异或操作和与操作得到结果,异或操作得到每一位上的数值,与操作得到需要进位的位置。每次相加需要将异或操作得到值和与操作得到的值左移一位相加,不断循环此操作,直到与操作得到的值为0,此时不需要进位,异或操作得到的值即为二进制相加的结果。下面为1203+1111的实例,对应的二进制为10010110011+10001010111。

1
2
 10010110011    000011100100    100011000010    100010001010    100000001010    100100001010
+10001010111 = +100000100110 = +000001001000 = +000010000000 = +000100000000 = +000000000000 = 100100001010(2314)

Java代码实现:

1
2
3
4
5
6
7
8
9
public int add(int a, int b) {
while (b != 0) {
int t = a ^ b;
b = (a & b) << 1;
a = t;
}

return a;
}

位运算相减

减运算直接转化为加运算即可,将减数转化为其相反数,直接与被减数相加。负数的补码是反码加一,最后附有Java位运算符号。

Java代码实现:

1
2
3
4
public int subtract(int a, int b) {
b = add(~b, 1);
return add(a, b);
}

位运算相乘

乘法运算用位移操作和加法操作,先忽略两个乘数的符号,取其绝对值进行相乘。以下为1203*1111的实例,对应二进制为10010110011*10001010111。

1
2
3
4
 10010110011    100101100110    1001011001100    10010110011000    100101100110000    100101100110000    1001011001100000    10010110011000000    100101100110000000    100101100110000000    1001011001100000000
*10001010111 = * 1000101011 = * 100010101 = * 10001010 = * 1000101 = * 100010 = * 10001 = * 1000 = * 100 = * 10 = * 1
———————————— ————————————— —————————————— ——————————————— ——————————————— ——————————————— ———————————————— ————————————————— —————————————————— —————————————————— ———————————————————
10010110011 + 100101100110 + 1001011001100 + 00000000000000 + 100101100110000 + 000000000000000 + 1001011001100000 + 00000000000000000 + 000000000000000000 + 000000000000000000 + 1001011001100000000

Java实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int multiply(int a, int b) {
//求a和b的绝对值
int multiplier = a < 0 ? add(~a, 1) : a;
int multiplicand = b < 0 ? add(~b, 1) : b;

//求两个绝对值的乘数
int product = 0;
while (multiplicand != 0) {
if ((multiplicand & 1) == 1) {
product += multiplier;
}

multiplier = multiplier << 1;
multiplicand = multiplicand >> 1;
}

//符号
if (add(a, b) < 0) {
product = add(~product, 1);
}

return product;
}

位运算相除

Java代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public int divide(int a, int b) {
//求a和b的绝对值
int dividend = a < 0 ? add(~a, 1) : a;
int divisor = b < 0 ? add(~b, 1) : b;

//求被除数倒过来的数
//以1为界限,后面的数为倒过来的数
int invert = 2;
while (dividend != 0) {
invert |= dividend & 1;
dividend = dividend >> 1;
invert = invert <<1;
}

//除数过程
//商
int quotient = 0;
//余数
int remainder = 0;
while (invert > 1) {
remainder = remainder << 1;
remainder |= invert & 1;
invert = invert >> 1;
quotient = quotient << 1;

if (remainder >= divisor) {
quotient |= 1;
remainder = subtract(remainder, divisor);
}
}

//符号
if (add(a, b) < 0) {
quotient = add(~quotient, 1);
}

return quotient;
}

Java位运算:

  • <<(左移)
  • >>(右移)
  • >>>(无符号右移)
  • &(与)
  • |(或)
  • ^(抑或)
  • ~(非)
-------------本文结束感谢您的阅读-------------

本文标题:位运算

文章作者:huihui

发布时间:2018年09月14日 - 10:09

最后更新:2019年02月14日 - 19:02

原始链接:http://101.200.47.120:8011/2018/09/14/位运算/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。