Java按位除法的实现

Question

    String n1="1010100000000010",n2="10000111";
    int div=Integer.parseInt(n1,2);
    int divisor=Integer.parseInt(n2,2);
    int div_Hi=0;

    for(int i=0;i<8;i++){

        dividend<<=1;

        if(dividend_Hi>=divisor){

            dividend_Hi-=divisor;
            dividend=dividend+1;

        }
    }

图中有一个二进制除法的算法。以下是我的问题：

如何初始化 dividend_Hi？
如何在代码中使用dividend_Lo？
我需要在代码中做哪些更正？

Answer 1

假设n是4，你想要8位数的高4位和低4位：

1 1 1 0 0 1 0 1
   ↓       ↓
   ↓    0 1 0 1
1 1 1 0

只需保持较低的 n 位就足够了，您只需屏蔽掉其余部分即可。在位逻辑中，这意味着与 00001111 的按位 AND，您可以通过将 1 左移 n，得到 10000，然后减去 [=16] 来计算=], 给你 1111.

lo = num & ((1 << n) - 1);

获得高位更容易。只需向右移动 n 位：

hi = num >>> n;

Answer 2

dividend_Hi 只是你的 2n 位红利的上半部分。因此，让我们假设您的股息是 6 (110)，除数是 2 (10)。 n 在本例中为 3，因为这是表示整数所需的最少位数。因此，对于 2n 位被除数 (2n = 6)，您只需用零 (000110) 填充左侧即可。

int dividend = 6;
int divisor  = 2;
int n1 = Integer.SIZE - Integer.numberOfLeadingZeros(dividend);
int n2 = Integer.SIZE - Integer.numberOfLeadingZeros(divisor);
int n = n1 >= n2 ? n1 : n2;
int dividend_Hi = dividend >> n;
int dividend_Lo = dividend & ((1 << n) - 1);

for (int i = 0; i < n; i++) {
    dividend <<= 1;
    dividend_Hi = dividend >> n;
    if (dividend_Hi >= divisor) {
        dividend_Hi -= divisor;
        dividend++;
    }
    dividend_Lo = dividend & ((1 << n) - 1);
    dividend = dividend_Hi << n | dividend_Lo;
}

Java按位除法的实现

Java implementation of bitwise division

java

binary

bit