ビットシフトと加算のみを使用して乗算と除算を行うにはどうすればよいですか?
282074 次
14 に答える
84
加算とシフトに関して乗算するには、次のように、数値の 1 つを 2 の累乗で分解します。
21 * 5 = 10101_2 * 101_2 (Initial step)
= 10101_2 * (1 * 2^2 + 0 * 2^1 + 1 * 2^0)
= 10101_2 * 2^2 + 10101_2 * 2^0
= 10101_2 << 2 + 10101_2 << 0 (Decomposed)
= 10101_2 * 4 + 10101_2 * 1
= 10101_2 * 5
= 21 * 5 (Same as initial expression)
(_2は基数 2 を意味します)
ご覧のとおり、乗算は加算とシフトに分解して、再び元に戻すことができます。これは、乗算がビット シフトや加算よりも時間がかかる理由でもあります。ビット数は O(n) ではなく O(n^2) です。実際のコンピューター システム (理論上のコンピューター システムとは対照的に) のビット数は有限であるため、乗算には、加算やシフトに比べて一定の倍数の時間がかかります。私の記憶が正しければ、最新のプロセッサは、適切にパイプライン化されていれば、プロセッサ内の ALU (算術演算ユニット) の使用率をいじることによって、加算とほぼ同じ速さで乗算を実行できます。
于 2010-05-05T22:31:12.667 に答える
45
アンドリュー・トゥールーズによる答えは除算に拡張できます。
整数定数による除算については、Henry S. Warren 著の書籍「Hacker's Delight」(ISBN 9780201914658) で詳しく説明されています。
割り算を実装するための最初のアイデアは、分母の逆数を基数 2 で書くことです。
例えば、
1/3 = (base-2) 0.0101 0101 0101 0101 0101 0101 0101 0101 .....
つまり、
a/3 = (a >> 2) + (a >> 4) + (a >> 6) + ... + (a >> 30)
32 ビット演算の場合です。
明白な方法で用語を組み合わせることで、操作の数を減らすことができます。
b = (a >> 2) + (a >> 4)
b += (b >> 4)
b += (b >> 8)
b += (b >> 16)
割り算と剰余を計算するもっと面白い方法があります。
EDIT1：
OPが定数による除算ではなく、任意の数値の乗算と除算を意味する場合、このスレッドが役立つ可能性があります: https://stackoverflow.com/a/12699549/1182653
EDIT2：
整数定数で割る最速の方法の 1 つは、剰余算術とモンゴメリー簡約を利用することです。整数を 3 で割る最速の方法は何ですか?
于 2012-04-25T23:37:22.240 に答える
31
X * 2 = 1 ビット左にシフト
X / 2 = 1 ビット右にシフト
X * 3 = 1 ビット左にシフトしてから X を加算
于 2010-05-05T19:38:13.600 に答える
28
x << k == x multiplied by 2 to the power of k
x >> k == x divided by 2 to the power of k
これらのシフトを使用して、任意の乗算操作を実行できます。例えば：
x * 14 == x * 16 - x * 2 == (x << 4) - (x << 1)
x * 12 == x * 8 + x * 4 == (x << 3) + (x << 2)
数値を 2 のべき乗以外で割るには、低レベルのロジックを実装したり、他のバイナリ演算を使用したり、何らかの形式の反復を使用したりしない限り、簡単な方法を知りません。
于 2010-05-05T19:44:09.060 に答える
18
- 1桁の左シフトは、2倍することに似ています。右シフトは、2で割ることに似ています。
- ループに追加して乗算できます。ループ変数と加算変数を正しく選択することで、パフォーマンスをバインドできます。それを調べたら、農民の乗算を使用する必要があります
于 2010-05-05T19:38:54.467 に答える
7
シフトと加算を使用する整数の除算手順は、小学校で教えられている 10 進数の除算から簡単に導き出すことができます。各商の桁の選択は、桁が 0 と 1 のいずれかであるため、単純化されています。現在の剰余が除数以上の場合、部分商の最下位ビットは 1 です。
10 進数の手書き除算と同様に、被除数の桁は最上位から最下位へと一度に 1 桁ずつ考慮されます。これは、2 進数除算の左シフトによって簡単に実現できます。また、商ビットは、現在の商ビットを 1 桁左にシフトし、新しい商ビットを追加することによって収集されます。
古典的な配置では、これらの 2 つの左シフトは、1 つのレジスタ ペアの左シフトに結合されます。上半分には現在の剰余が保持され、下半分の初期には被除数が保持されます。被除数ビットは左シフトによって剰余レジスタに転送されるため、下位半分の未使用の最下位ビットが商ビットの累算に使用されます。
以下は、このアルゴリズムの x86 アセンブリ言語と C 実装です。シフト & 加算除算のこの特定の変形は、剰余が除数以上でない限り、現在の剰余からの除数の減算が実行されないため、「非実行」変形と呼ばれることがあります (Otto Spaniol, 「コンピュータ演算: 論理と設計」チチェスター: Wiley 1981、p. 144)。C では、レジスタ ペアの左シフトのアセンブリ バージョンで使用されるキャリー フラグの概念はありません。代わりに、2 nを法とする加算の結果は、キャリーアウトがあった場合にのみ、いずれかの加数よりも小さくなる可能性があるという観察に基づいて、エミュレートされます。
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define USE_ASM 0
#if USE_ASM
uint32_t bitwise_division (uint32_t dividend, uint32_t divisor)
{
uint32_t quot;
__asm {
mov eax, [dividend];// quot = dividend
mov ecx, [divisor]; // divisor
mov edx, 32; // bits_left
mov ebx, 0; // rem
$div_loop:
add eax, eax; // (rem:quot) << 1
adc ebx, ebx; // ...
cmp ebx, ecx; // rem >= divisor ?
jb $quot_bit_is_0; // if (rem < divisor)
$quot_bit_is_1: //
sub ebx, ecx; // rem = rem - divisor
add eax, 1; // quot++
$quot_bit_is_0:
dec edx; // bits_left--
jnz $div_loop; // while (bits_left)
mov [quot], eax; // quot
}
return quot;
}
#else
uint32_t bitwise_division (uint32_t dividend, uint32_t divisor)
{
uint32_t quot, rem, t;
int bits_left = CHAR_BIT * sizeof (uint32_t);
quot = dividend;
rem = 0;
do {
// (rem:quot) << 1
t = quot;
quot = quot + quot;
rem = rem + rem + (quot < t);
if (rem >= divisor) {
rem = rem - divisor;
quot = quot + 1;
}
bits_left--;
} while (bits_left);
return quot;
}
#endif
于 2015-09-07T17:05:01.917 に答える
6
私は Python コードを C に翻訳しました。与えられた例には小さな欠陥がありました。被除数が 32 ビットすべてを占める場合、シフトは失敗します。この問題を回避するために、内部で 64 ビット変数を使用しました。
int No_divide(int nDivisor, int nDividend, int *nRemainder)
{
int nQuotient = 0;
int nPos = -1;
unsigned long long ullDivisor = nDivisor;
unsigned long long ullDividend = nDividend;
while (ullDivisor < ullDividend)
{
ullDivisor <<= 1;
nPos ++;
}
ullDivisor >>= 1;
while (nPos > -1)
{
if (ullDividend >= ullDivisor)
{
nQuotient += (1 << nPos);
ullDividend -= ullDivisor;
}
ullDivisor >>= 1;
nPos -= 1;
}
*nRemainder = (int) ullDividend;
return nQuotient;
}
于 2013-11-05T02:04:37.497 に答える
4
2 つの数字、たとえば 9 と 10 を 2 進数で書きます - 1001 と 1010。
0 の結果 R から始めます。
数字の 1 つ、この場合は 1010 を取り、それを A と呼び、1 ビット右にシフトします。1 をシフトアウトする場合は、最初の数字 (B と呼びます) を R に追加します。
次に、B を 1 ビット左にシフトし、すべてのビットが A からシフトアウトされるまで繰り返します。
書き出されたものを見ると、何が起こっているかを簡単に確認できます。これは例です。
0
0000 0
10010 1
000000 0
1001000 1
------
1011010
于 2010-05-05T22:11:02.793 に答える
1
以下の方法は、両方の数値が正であることを考慮したバイナリ除算の実装です。減算が懸念される場合は、2 項演算子を使用して実装することもできます。
コード
-(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);
}
乗算の場合:
-(int)multiplyNumber:(int)num1 withNumber:(int)num2
{
int mulResult = 0;
int ithBit;
BOOL isNegativeSign = (num1<0 && num2>0) || (num1>0 && num2<0);
num1 = abs(num1);
num2 = abs(num2);
for (int i=0; i<sizeof(num2)*8; i++)
{
ithBit = num2 & (1<<i);
if (ithBit>0) {
mulResult += (num1 << i);
}
}
if (isNegativeSign) {
mulResult = ((~mulResult)+1);
}
return mulResult;
}
于 2014-02-12T20:37:38.897 に答える
1
This should work for multiplication:
.data
.text
.globl main
main:
# $4 * $5 = $2
addi $4, $0, 0x9
addi $5, $0, 0x6
add $2, $0, $0 # initialize product to zero
Loop:
beq $5, $0, Exit # if multiplier is 0,terminate loop
andi $3, $5, 1 # mask out the 0th bit in multiplier
beq $3, $0, Shift # if the bit is 0, skip add
addu $2, $2, $4 # add (shifted) multiplicand to product
Shift:
sll $4, $4, 1 # shift up the multiplicand 1 bit
srl $5, $5, 1 # shift down the multiplier 1 bit
j Loop # go for next
Exit: #
EXIT:
li $v0,10
syscall
于 2012-09-13T23:44:45.033 に答える
1
それは基本的に底乗2で乗算および除算されます
左シフト = x * 2 ^ y
右シフト = x / 2 ^ y
shl eax,2 = 2 * 2 ^ 2 = 8
shr eax,3 = 2 / 2 ^ 3 = 1/4
于 2020-05-28T09:54:05.613 に答える
0
16 ビットの x86 ソリューションに興味がある人のために、JasonKnightによるコードの一部をここに示します1 (彼には、署名付きの乗算部分も含まれていますが、私はテストしていません)。ただし、そのコードには、「add bx,bx」部分がオーバーフローする大規模な入力に関する問題があります。
修正版:
softwareMultiply:
; INPUT CX,BX
; OUTPUT DX:AX - 32 bits
; CLOBBERS BX,CX,DI
xor ax,ax ; cheap way to zero a reg
mov dx,ax ; 1 clock faster than xor
mov di,cx
or di,bx ; cheap way to test for zero on both regs
jz @done
mov di,ax ; DI used for reg,reg adc
@loop:
shr cx,1 ; divide by two, bottom bit moved to carry flag
jnc @skipAddToResult
add ax,bx
adc dx,di ; reg,reg is faster than reg,imm16
@skipAddToResult:
add bx,bx ; faster than shift or mul
adc di,di
or cx,cx ; fast zero check
jnz @loop
@done:
ret
または、GCC インライン アセンブリでも同じです。
asm("mov $0,%%ax\n\t"
"mov $0,%%dx\n\t"
"mov %%cx,%%di\n\t"
"or %%bx,%%di\n\t"
"jz done\n\t"
"mov %%ax,%%di\n\t"
"loop:\n\t"
"shr $1,%%cx\n\t"
"jnc skipAddToResult\n\t"
"add %%bx,%%ax\n\t"
"adc %%di,%%dx\n\t"
"skipAddToResult:\n\t"
"add %%bx,%%bx\n\t"
"adc %%di,%%di\n\t"
"or %%cx,%%cx\n\t"
"jnz loop\n\t"
"done:\n\t"
: "=d" (dx), "=a" (ax)
: "b" (bx), "c" (cx)
: "ecx", "edi"
);
于 2015-07-14T01:38:27.460 に答える