当前位置： 文江博客话题详情

使用按位运算符实现除法

发布于 2024-10-21 12:05:21 字数 50 浏览 2 评论 0原文

如何使用按位运算符实现除法（不仅仅是除以 2 的幂）？

详细描述一下。

原文

How can I implement division using bit-wise operators (not just division by powers of 2)?

Describe it in detail.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（13）

够钟 2024-10-28 12:05:21

进行除法的标准方法是实现二进制长除法。这涉及减法，因此只要您不将其视为不是按位运算，那么这就是您应该做的。 （请注意，您当然可以使用按位逻辑运算实现减法，非常繁琐。）

本质上，如果您正在执行 Q = N/D：

  1. 对齐 的最高有效位N 和 D。
  2. 计算t = (N - D);。
  3. 如果(t >= 0)，则将Q的最低有效位设置为1，并设置N = t。
  4. 将 N 左移 1。
  5. 将 Q 左移 1。
  6. 转到步骤 2。

根据需要循环获取尽可能多的输出位（包括小数），然后应用最后一班撤消您在步骤 1 中所做的操作。

The standard way to do division is by implementing binary long-division. This involves subtraction, so as long as you don't discount this as not a bit-wise operation, then this is what you should do. (Note that you can of course implement subtraction, very tediously, using bitwise logical operations.)

In essence, if you're doing Q = N/D:

  1. Align the most-significant ones of N and D.
  2. Compute t = (N - D);.
  3. If (t >= 0), then set the least significant bit of Q to 1, and set N = t.
  4. Left-shift N by 1.
  5. Left-shift Q by 1.
  6. Go to step 2.

Loop for as many output bits (including fractional) as you require, then apply a final shift to undo what you did in Step 1.

回复 原文
π浅易 2024-10-28 12:05:21

使用按位运算符对两个数字进行除法。

#include <stdio.h>

int remainder, divisor;

int division(int tempdividend, int tempdivisor) {
    int quotient = 1;

    if (tempdivisor == tempdividend) {
        remainder = 0;
        return 1;
    } else if (tempdividend < tempdivisor) {
        remainder = tempdividend;
        return 0;
    }   

    do{

        tempdivisor = tempdivisor << 1;
        quotient = quotient << 1;

     } while (tempdivisor <= tempdividend);


     /* Call division recursively */
    quotient = quotient + division(tempdividend - tempdivisor, divisor);

    return quotient;
} 


int main() {
    int dividend;

    printf ("\nEnter the Dividend: ");
    scanf("%d", ÷nd);
    printf("\nEnter the Divisor: ");
    scanf("%d", &divisor);   

    printf("\n%d / %d: quotient = %d", dividend, divisor, division(dividend, divisor));
    printf("\n%d / %d: remainder = %d", dividend, divisor, remainder);
    getch();
}

Division of two numbers using bitwise operators.

#include <stdio.h>

int remainder, divisor;

int division(int tempdividend, int tempdivisor) {
    int quotient = 1;

    if (tempdivisor == tempdividend) {
        remainder = 0;
        return 1;
    } else if (tempdividend < tempdivisor) {
        remainder = tempdividend;
        return 0;
    }   

    do{

        tempdivisor = tempdivisor << 1;
        quotient = quotient << 1;

     } while (tempdivisor <= tempdividend);


     /* Call division recursively */
    quotient = quotient + division(tempdividend - tempdivisor, divisor);

    return quotient;
} 


int main() {
    int dividend;

    printf ("\nEnter the Dividend: ");
    scanf("%d", ÷nd);
    printf("\nEnter the Divisor: ");
    scanf("%d", &divisor);   

    printf("\n%d / %d: quotient = %d", dividend, divisor, division(dividend, divisor));
    printf("\n%d / %d: remainder = %d", dividend, divisor, remainder);
    getch();
}
回复 原文
穿越时光隧道 2024-10-28 12:05:21
int remainder =0;

int division(int dividend, int divisor)
{
    int quotient = 1;

    int neg = 1;
    if ((dividend>0 &&divisor<0)||(dividend<0 && divisor>0))
        neg = -1;

    // Convert to positive
    unsigned int tempdividend = (dividend < 0) ? -dividend : dividend;
    unsigned int tempdivisor = (divisor < 0) ? -divisor : divisor;

    if (tempdivisor == tempdividend) {
        remainder = 0;
        return 1*neg;
    }
    else if (tempdividend < tempdivisor) {
        if (dividend < 0)
            remainder = tempdividend*neg;
        else
            remainder = tempdividend;
        return 0;
    }
    while (tempdivisor<<1 <= tempdividend)
    {
        tempdivisor = tempdivisor << 1;
        quotient = quotient << 1;
    }

    // Call division recursively
    if(dividend < 0)
        quotient = quotient*neg + division(-(tempdividend-tempdivisor), divisor);
    else
        quotient = quotient*neg + division(tempdividend-tempdivisor, divisor);
     return quotient;
 }


void main()
{
    int dividend,divisor;
    char ch = 's';
    while(ch != 'x')
    {
        printf ("\nEnter the Dividend: ");
        scanf("%d", ÷nd);
        printf("\nEnter the Divisor: ");
        scanf("%d", &divisor);

        printf("\n%d / %d: quotient = %d", dividend, divisor, division(dividend, divisor));
        printf("\n%d / %d: remainder = %d", dividend, divisor, remainder);

        _getch();
    }
}

int remainder =0;

int division(int dividend, int divisor)
{
    int quotient = 1;

    int neg = 1;
    if ((dividend>0 &&divisor<0)||(dividend<0 && divisor>0))
        neg = -1;

    // Convert to positive
    unsigned int tempdividend = (dividend < 0) ? -dividend : dividend;
    unsigned int tempdivisor = (divisor < 0) ? -divisor : divisor;

    if (tempdivisor == tempdividend) {
        remainder = 0;
        return 1*neg;
    }
    else if (tempdividend < tempdivisor) {
        if (dividend < 0)
            remainder = tempdividend*neg;
        else
            remainder = tempdividend;
        return 0;
    }
    while (tempdivisor<<1 <= tempdividend)
    {
        tempdivisor = tempdivisor << 1;
        quotient = quotient << 1;
    }

    // Call division recursively
    if(dividend < 0)
        quotient = quotient*neg + division(-(tempdividend-tempdivisor), divisor);
    else
        quotient = quotient*neg + division(tempdividend-tempdivisor, divisor);
     return quotient;
 }


void main()
{
    int dividend,divisor;
    char ch = 's';
    while(ch != 'x')
    {
        printf ("\nEnter the Dividend: ");
        scanf("%d", ÷nd);
        printf("\nEnter the Divisor: ");
        scanf("%d", &divisor);

        printf("\n%d / %d: quotient = %d", dividend, divisor, division(dividend, divisor));
        printf("\n%d / %d: remainder = %d", dividend, divisor, remainder);

        _getch();
    }
}
回复 原文
短叹 2024-10-28 12:05:21

我假设我们正在讨论整数除法。

假设我有两个数字 1502 和 30，我想计算 1502/30。我们是这样做的：

首先，我们将 30 与 1501 的最高位数字对齐； 30 变成 3000。然后将 1501 与 3000 进行比较，1501 包含 3000 中的 0。然后我们将 1501 与 300 进行比较，它包含 300 中的 5，然后将 (1501-5300) 与 30 进行比较。最后我们得到 5 (10^1) = 50 作为此除法的结果。

现在将 1501 和 30 都转换为二进制数字。然后，我们不是将 30 乘以 (10^x) 以将其与 1501 对齐，而是将 2 进制的 (30) 乘以 2^n 来对齐。而2^n可以转化为左移n个位置。

这是代码：

int divide(int a, int b){
    if (b != 0)
        return;

    //To check if a or b are negative.
    bool neg = (a > 0) == (b > 0);

    //Convert to positive
    unsigned int new_a = (a < 0) ? -a : a;
    unsigned int new_b = (b < 0) ? -b : b;

    //Check the largest n such that b >= 2^n, and assign the n to n_pwr
    int n_pwr = 0;
    for (int i = 0; i < 32; i++)
    {
        if (((1 << i) & new_b) != 0)
            n_pwr = i;
    }

    //So that 'a' could only contain 2^(31-n_pwr) many b's,
    //start from here to try the result
    unsigned int res = 0;
    for (int i = 31 - n_pwr; i >= 0; i--){
        if ((new_b << i) <= new_a){
            res += (1 << i);
            new_a -= (new_b << i);
        }
    }

    return neg ? -res : res;
}

没有测试它，但你明白了。

I assume we are discussing division of integers.

Consider that I got two number 1502 and 30, and I wanted to calculate 1502/30. This is how we do this:

First we align 30 with 1501 at its most significant figure; 30 becomes 3000. And compare 1501 with 3000, 1501 contains 0 of 3000. Then we compare 1501 with 300, it contains 5 of 300, then compare (1501-5300) with 30. At so at last we got 5(10^1) = 50 as the result of this division.

Now convert both 1501 and 30 into binary digits. Then instead of multiplying 30 with (10^x) to align it with 1501, we multiplying (30) in 2 base with 2^n to align. And 2^n can be converted into left shift n positions.

Here is the code:

int divide(int a, int b){
    if (b != 0)
        return;

    //To check if a or b are negative.
    bool neg = (a > 0) == (b > 0);

    //Convert to positive
    unsigned int new_a = (a < 0) ? -a : a;
    unsigned int new_b = (b < 0) ? -b : b;

    //Check the largest n such that b >= 2^n, and assign the n to n_pwr
    int n_pwr = 0;
    for (int i = 0; i < 32; i++)
    {
        if (((1 << i) & new_b) != 0)
            n_pwr = i;
    }

    //So that 'a' could only contain 2^(31-n_pwr) many b's,
    //start from here to try the result
    unsigned int res = 0;
    for (int i = 31 - n_pwr; i >= 0; i--){
        if ((new_b << i) <= new_a){
            res += (1 << i);
            new_a -= (new_b << i);
        }
    }

    return neg ? -res : res;
}

Didn't test it, but you get the idea.

回复 原文
九公里浅绿 2024-10-28 12:05:21

这个解决方案效果很好。

#include <stdio.h>

int division(int dividend, int divisor, int origdiv, int * remainder)
{
    int quotient = 1;

    if (dividend == divisor)
    {
        *remainder = 0;
        return 1;
    }

    else if (dividend < divisor)
    {
        *remainder = dividend;
        return 0;
    }

    while (divisor <= dividend)
    {
        divisor = divisor << 1;
        quotient = quotient << 1;
    }

    if (dividend < divisor)
    {
        divisor >>= 1;
        quotient >>= 1;
    }

    quotient = quotient + division(dividend - divisor, origdiv, origdiv, remainder);

    return quotient;
}

int main()
{
    int n = 377;
    int d = 7;
    int rem = 0;

    printf("Quotient : %d\n", division(n, d, d, &rem));
    printf("Remainder: %d\n", rem);

    return 0;
}

This solution works perfectly.

#include <stdio.h>

int division(int dividend, int divisor, int origdiv, int * remainder)
{
    int quotient = 1;

    if (dividend == divisor)
    {
        *remainder = 0;
        return 1;
    }

    else if (dividend < divisor)
    {
        *remainder = dividend;
        return 0;
    }

    while (divisor <= dividend)
    {
        divisor = divisor << 1;
        quotient = quotient << 1;
    }

    if (dividend < divisor)
    {
        divisor >>= 1;
        quotient >>= 1;
    }

    quotient = quotient + division(dividend - divisor, origdiv, origdiv, remainder);

    return quotient;
}

int main()
{
    int n = 377;
    int d = 7;
    int rem = 0;

    printf("Quotient : %d\n", division(n, d, d, &rem));
    printf("Remainder: %d\n", rem);

    return 0;
}
回复 原文
递刀给你 2024-10-28 12:05:21

不使用除法运算符实现除法：
您将需要包括减法。但这就像你手工做的一样（仅以 2 为基础）。附加的代码提供了一个简短的函数来完成此任务。

uint32_t udiv32(uint32_t n, uint32_t d) {
    // n is dividend, d is divisor
    // store the result in q: q = n / d
    uint32_t q = 0;

    // as long as the divisor fits into the remainder there is something to do
    while (n >= d) {
        uint32_t i = 0, d_t = d;
        // determine to which power of two the divisor still fits the dividend
        //
        // i.e.: we intend to subtract the divisor multiplied by powers of two
        // which in turn gives us a one in the binary representation 
        // of the result
        while (n >= (d_t << 1) && ++i)
            d_t <<= 1;
        // set the corresponding bit in the result
        q |= 1 << i;
        // subtract the multiple of the divisor to be left with the remainder
        n -= d_t;
        // repeat until the divisor does not fit into the remainder anymore
    }
    return q;
}

Implement division without divison operator:
You will need to include subtraction. But then it is just like you do it by hand (only in the basis of 2). The appended code provides a short function that does exactly this.

uint32_t udiv32(uint32_t n, uint32_t d) {
    // n is dividend, d is divisor
    // store the result in q: q = n / d
    uint32_t q = 0;

    // as long as the divisor fits into the remainder there is something to do
    while (n >= d) {
        uint32_t i = 0, d_t = d;
        // determine to which power of two the divisor still fits the dividend
        //
        // i.e.: we intend to subtract the divisor multiplied by powers of two
        // which in turn gives us a one in the binary representation 
        // of the result
        while (n >= (d_t << 1) && ++i)
            d_t <<= 1;
        // set the corresponding bit in the result
        q |= 1 << i;
        // subtract the multiple of the divisor to be left with the remainder
        n -= d_t;
        // repeat until the divisor does not fit into the remainder anymore
    }
    return q;
}
回复 原文
狼性发作 2024-10-28 12:05:21

无符号长除法 (JavaScript) - 基于维基百科文章：https://en.wikipedia.org/wiki/除法算法：
“长除法是用于以十进制表示的多位数字的笔和纸除法的标准算法。它从被除数的左端逐渐移动到右端，减去除数的最大可能倍数（在每个阶段的倍数就变成商的位数，最后的差就是余数。
当与二进制基数一起使用时，此方法构成了下面的（无符号）整数除法与余数算法的基础。“

最后的函数divideWithoutDivision将其包装以允许负操作数。我用它来解决leetcode问题“除Self之外的数组的乘积”

function longDivision(N, D) {
    let Q = 0; //quotient and remainder
    let R = 0;
    let n = mostSignificantBitIn(N);
    for (let i = n; i >= 0; i--) { 
        R = R << 1;
        R = setBit(R, 0, getBit(N, i));
        if (R >= D) {
            R = R - D;
            Q = setBit(Q, i, 1);
        }
    }
    //return [Q, R];
    return Q;
}
function mostSignificantBitIn(N) {
    for (let i = 31; i >= 0; i--) {
        if (N & (1 << i))
            return i ;
    }
    return 0;
}
function getBit(N, i) {
    return (N & (1 << i)) >> i;
}
function setBit(N, i, value) {
    return N | (value << i);
}
function divideWithoutDivision(dividend, divisor) {
    let negativeResult = (dividend < 0) ^ (divisor < 0);
    dividend = Math.abs(dividend);
    divisor = Math.abs(divisor);
    let quotient = longDivision(dividend, divisor);
    return negativeResult ? -quotient : quotient;
}

Unsigned Long Division (JavaScript) - based on Wikipedia article: https://en.wikipedia.org/wiki/Division_algorithm:
"Long division is the standard algorithm used for pen-and-paper division of multi-digit numbers expressed in decimal notation. It shifts gradually from the left to the right end of the dividend, subtracting the largest possible multiple of the divisor (at the digit level) at each stage; the multiples then become the digits of the quotient, and the final difference is then the remainder.
When used with a binary radix, this method forms the basis for the (unsigned) integer division with remainder algorithm below."

Function divideWithoutDivision at the end wraps it to allow negative operands. I used it to solve leetcode problem "Product of Array Except Self"

function longDivision(N, D) {
    let Q = 0; //quotient and remainder
    let R = 0;
    let n = mostSignificantBitIn(N);
    for (let i = n; i >= 0; i--) { 
        R = R << 1;
        R = setBit(R, 0, getBit(N, i));
        if (R >= D) {
            R = R - D;
            Q = setBit(Q, i, 1);
        }
    }
    //return [Q, R];
    return Q;
}
function mostSignificantBitIn(N) {
    for (let i = 31; i >= 0; i--) {
        if (N & (1 << i))
            return i ;
    }
    return 0;
}
function getBit(N, i) {
    return (N & (1 << i)) >> i;
}
function setBit(N, i, value) {
    return N | (value << i);
}
function divideWithoutDivision(dividend, divisor) {
    let negativeResult = (dividend < 0) ^ (divisor < 0);
    dividend = Math.abs(dividend);
    divisor = Math.abs(divisor);
    let quotient = longDivision(dividend, divisor);
    return negativeResult ? -quotient : quotient;
}
回复 原文
被翻牌 2024-10-28 12:05:21

下面的方法是考虑到两个数字都是正数的二进制除法的实现。如果需要考虑减法，我们也可以使用二元运算符来实现。

代码

-(int)binaryDivide:(int)numerator with:(int)denominator
{
    if (numerator == 0 || denominator == 1) {
        return numerator;
    }

    if (denominator == 0) {

        #ifdef DEBUG
            NSAssert(denominator == 0, @"denominator should be greater then 0");
        #endif
        return INFINITY;
    }

    // if (numerator <0) {
    //     numerator = abs(numerator);
    // }

    int maxBitDenom = [self getMaxBit:denominator];
    int maxBitNumerator = [self getMaxBit:numerator];
    int msbNumber = [self getMSB:maxBitDenom ofNumber:numerator];

    int qoutient = 0;

    int subResult = 0;

    int remainingBits = maxBitNumerator-maxBitDenom;

    if (msbNumber >= denominator) {
        qoutient |=1;
        subResult = msbNumber - denominator;
    }
    else {
        subResult = msbNumber;
    }

    while (remainingBits>0) {
        int msbBit = (numerator & (1 << (remainingBits-1)))>0 ? 1 : 0;
        subResult = (subResult << 1) |msbBit;
        if (subResult >= denominator) {
            subResult = subResult-denominator;
            qoutient = (qoutient << 1) | 1;
        }
        else {
            qoutient = qoutient << 1;
        }
        remainingBits--;
    }
    return qoutient;
}


-(int)getMaxBit:(int)inputNumber
{
    int maxBit =0;
    BOOL isMaxBitSet = NO;
    for (int i=0; i<sizeof(inputNumber)*8; i++) {
        if (inputNumber & (1 << i) ) {
            maxBit = i;
            isMaxBitSet=YES;
        }
    }
    if (isMaxBitSet) {
        maxBit += 1;
    }
    return maxBit;
}


-(int)getMSB:(int)bits ofNumber:(int)number
{
    int numbeMaxBit = [self getMaxBit:number];
    return number >> (numbeMaxBit -bits);
}

The below method is the implementation of binary divide considering both numbers are positive. If subtraction is a concern we can implement that as well using binary operators.

Code

-(int)binaryDivide:(int)numerator with:(int)denominator
{
    if (numerator == 0 || denominator == 1) {
        return numerator;
    }

    if (denominator == 0) {

        #ifdef DEBUG
            NSAssert(denominator == 0, @"denominator should be greater then 0");
        #endif
        return INFINITY;
    }

    // if (numerator <0) {
    //     numerator = abs(numerator);
    // }

    int maxBitDenom = [self getMaxBit:denominator];
    int maxBitNumerator = [self getMaxBit:numerator];
    int msbNumber = [self getMSB:maxBitDenom ofNumber:numerator];

    int qoutient = 0;

    int subResult = 0;

    int remainingBits = maxBitNumerator-maxBitDenom;

    if (msbNumber >= denominator) {
        qoutient |=1;
        subResult = msbNumber - denominator;
    }
    else {
        subResult = msbNumber;
    }

    while (remainingBits>0) {
        int msbBit = (numerator & (1 << (remainingBits-1)))>0 ? 1 : 0;
        subResult = (subResult << 1) |msbBit;
        if (subResult >= denominator) {
            subResult = subResult-denominator;
            qoutient = (qoutient << 1) | 1;
        }
        else {
            qoutient = qoutient << 1;
        }
        remainingBits--;
    }
    return qoutient;
}


-(int)getMaxBit:(int)inputNumber
{
    int maxBit =0;
    BOOL isMaxBitSet = NO;
    for (int i=0; i<sizeof(inputNumber)*8; i++) {
        if (inputNumber & (1 << i) ) {
            maxBit = i;
            isMaxBitSet=YES;
        }
    }
    if (isMaxBitSet) {
        maxBit += 1;
    }
    return maxBit;
}


-(int)getMSB:(int)bits ofNumber:(int)number
{
    int numbeMaxBit = [self getMaxBit:number];
    return number >> (numbeMaxBit -bits);
}
回复 原文
薄荷→糖丶微凉 2024-10-28 12:05:21

对于整数：

public class Division {

    public static void main(String[] args) {
        System.out.println("Division: " + divide(100, 9));
    }

    public static int divide(int num, int divisor) {
        int sign = 1;
        if((num > 0 && divisor < 0) || (num < 0 && divisor > 0))
            sign = -1;

        return divide(Math.abs(num), Math.abs(divisor), Math.abs(divisor)) * sign;
    }

    public static int divide(int num, int divisor, int sum) {
        if (sum > num) {
            return 0;
        }

        return 1 + divide(num, divisor, sum + divisor);
    }
}

For integers:

public class Division {

    public static void main(String[] args) {
        System.out.println("Division: " + divide(100, 9));
    }

    public static int divide(int num, int divisor) {
        int sign = 1;
        if((num > 0 && divisor < 0) || (num < 0 && divisor > 0))
            sign = -1;

        return divide(Math.abs(num), Math.abs(divisor), Math.abs(divisor)) * sign;
    }

    public static int divide(int num, int divisor, int sum) {
        if (sum > num) {
            return 0;
        }

        return 1 + divide(num, divisor, sum + divisor);
    }
}
回复 原文
月亮是我掰弯的 2024-10-28 12:05:21

对于 C 的移位行为的常见警告，这应该适用于无符号数量，无论 int 的本机大小如何...

static unsigned int udiv(unsigned int a, unsigned int b) {
  unsigned int c = 1, result = 0;

  if (b == 0) return (unsigned int)-1 /*infinity*/;

  while (((int)b > 0) && (b < a)) { b = b<<1; c = c<<1; }

  do {
    if (a >= b) { a -= b; result += c; }
    b = b>>1; c = c>>1;
  } while (c);

  return result;
}

With the usual caveats about C's behaviour with shifts, this ought to work for unsigned quantities regardless of the native size of an int...

static unsigned int udiv(unsigned int a, unsigned int b) {
  unsigned int c = 1, result = 0;

  if (b == 0) return (unsigned int)-1 /*infinity*/;

  while (((int)b > 0) && (b < a)) { b = b<<1; c = c<<1; }

  do {
    if (a >= b) { a -= b; result += c; }
    b = b>>1; c = c>>1;
  } while (c);

  return result;
}
回复 原文
甜扑 2024-10-28 12:05:21

这是我仅使用按位运算实现除法的解决方案：

int align(int a, int b) {
  while (b < a) b <<= 1;
  return b;
}

int divide(int a, int b) {
  int temp = b;
  int result = 0;
  b = align(a, b);
  do {
    result <<= 1;
    if (a >= b) {
      // sub(a,b) is a self-defined bitwise function for a minus b
      a = sub(a,b);
      result = result | 1;
    }
    b >>= 1;
  } while (b >= temp);
  return result;
}

This is my solution to implement division with only bitwise operations:

int align(int a, int b) {
  while (b < a) b <<= 1;
  return b;
}

int divide(int a, int b) {
  int temp = b;
  int result = 0;
  b = align(a, b);
  do {
    result <<= 1;
    if (a >= b) {
      // sub(a,b) is a self-defined bitwise function for a minus b
      a = sub(a,b);
      result = result | 1;
    }
    b >>= 1;
  } while (b >= temp);
  return result;
}
回复 原文
梦太阳 2024-10-28 12:05:21

所有这些解决方案都太长了。基本思想是将商（例如 5=101）写为 100 + 00 + 1 = 101。

public static Point divide(int a, int b) {

    if (a < b)
        return new Point(0,a);
    if (a == b)
        return new Point(1,0);
    int q = b;
    int c = 1;
    while (q<<1 < a) {
        q <<= 1;
        c <<= 1;
    }
    Point r = divide(a-q, b);
    return new Point(c + r.x, r.y);
}


public static class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int compare(Point b) {
        if (b.x - x != 0) {
            return x - b.x;
        } else {
            return y - b.y;
        }
    }

    @Override
    public String toString() {
        return " (" + x + " " + y + ") ";
    }
}

All these solutions are too long. The base idea is to write the quotient (for example, 5=101) as 100 + 00 + 1 = 101.

public static Point divide(int a, int b) {

    if (a < b)
        return new Point(0,a);
    if (a == b)
        return new Point(1,0);
    int q = b;
    int c = 1;
    while (q<<1 < a) {
        q <<= 1;
        c <<= 1;
    }
    Point r = divide(a-q, b);
    return new Point(c + r.x, r.y);
}


public static class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int compare(Point b) {
        if (b.x - x != 0) {
            return x - b.x;
        } else {
            return y - b.y;
        }
    }

    @Override
    public String toString() {
        return " (" + x + " " + y + ") ";
    }
}
回复 原文
戴着白色围巾的女孩 2024-10-28 12:05:21

由于按位运算适用于 0 或 1 的位，因此每个位代表 2 的幂，因此如果我有位

1010

，则该值是 10。

每个位都是 2 的幂，因此如果我们将位移至对，我们除以 2

1010 --> 0101

0101 是 5

，所以，一般来说，如果你想除以 2 的某个幂，你需要右移你提高 2 到的指数，以获得该值，

例如，要除以 16，你需要除以 4 ，如 2^^4 = 16。

Since bit wise operations work on bits that are either 0 or 1, each bit represents a power of 2, so if I have the bits

1010

that value is 10.

Each bit is a power of two, so if we shift the bits to the right, we divide by 2

1010 --> 0101

0101 is 5

so, in general if you want to divide by some power of 2, you need to shift right by the exponent you raise two to, to get that value

so for instance, to divide by 16, you would shift by 4, as 2^^4 = 16.

回复 原文
~没有更多了~

关于作者

醉酒的小男人

暂无简介

0 文章
0 评论
1048 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

烙印

文章 0 评论 0

singlesman

文章 0 评论 0

给自己一个微笑

文章 0 评论 0

独孤求败

文章 0 评论 0

晨钟暮鼓

文章 0 评论 0

我是自愿种绣球花的

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文