如何使用按位运算符实现除法（不仅仅是除以 2 的幂）？
详细描述一下。
进行除法的标准方法是实现二进制长除法。这涉及减法，因此只要您不将其视为不是按位运算，那么这就是您应该做的。 （请注意，您当然可以使用按位逻辑运算来实现减法，非常繁琐。）
本质上，如果你正在做
Q = N/DNDt = (N - D);(t >= 0)QN = tNQ根据需要循环获取尽可能多的输出位（包括小数），然后应用最后的移位来撤消您在步骤 1 中所做的操作。
使用按位运算符将两个数字相除。
#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();
}
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();
}
}
我假设我们正在讨论整数除法。
考虑一下我有两个数字 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;
}
没有测试过，但你明白了。
这个解决方案非常有效。
#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;
}
不使用除法运算符实现除法： 您将需要包括减法。但这就像你手工做的一样（仅以 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;
}
下面的方法是考虑到两个数字都是正数的情况下的二元除法的实现。如果需要考虑减法，我们也可以使用二元运算符来实现。
-(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);
}
对于整数：
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);
}
}
关于 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;
}
这是我仅使用按位运算实现除法的解决方案：
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;
}
无符号长除法 (JavaScript) - 基于维基百科文章：https://en.wikipedia.org/wiki/Division_algorithm： “长除法是用于以十进制表示的多位数字的笔和纸除法的标准算法。它从被除数的左端逐渐移动到右端，减去除数的最大可能倍数（在每个阶段的倍数变为商的位数，最后的差值就是余数。 当与二进制基数一起使用时，此方法构成了下面的（无符号）整数除法与余数算法的基础。”
最后的函数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;
}
所有这些解决方案都太长了。基本思想是将商（例如 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 + ") ";
}
}
由于按位运算适用于 0 或 1 位，因此每个位代表 2 的幂，所以如果我有这些位
1010
该值为 10。
每一位都是 2 的幂，所以如果我们将这些位向右移动，我们就会除以 2
1010 --> 0101
0101 是 5
所以，一般来说，如果你想除以 2 的某个幂，你需要右移你将 2 提高到的指数，以获得该值
例如，要除以 16，您需要移位 4，即 2^^4 = 16。