비트 시프트와 덧셈만을 사용하여 어떻게 곱하고 나눌 수 있습니까?
비트 시프트와 덧셈만을 사용하여 어떻게 곱하고 나눌 수 있습니까?
더하기 및 이동과 관련하여 곱하려면 다음과 같이 숫자 중 하나를 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(산술 단위)의 활용을 방해함으로써 곱셈을 덧셈과 거의 같은 속도로 할 수 있다.
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의 비제곱으로 나누려면, 저는 어떤 쉬운 방법도 모릅니다. 단, 어떤 낮은 수준의 논리를 구현하거나, 다른 이진 연산을 사용하거나, 어떤 형태의 반복을 사용하기를 원하지 않는 한 말입니다.
정수 상수에 의한 나눗셈은 헨리 S.의 "해커의 기쁨"에서 자세히 고려된다.Warren(ISBN 9780201914658)
나눗셈을 실시하기 위한 첫 번째 아이디어는 분모의 역값을 기저 2에 쓰는 것입니다.
,,1/3 = (base-2) 0.0101 0101 0101 0101 0101 0101 0101 0101 .....
so,는,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)
나눗셈과 잔량을 계산하는 더 흥미로운 방법이 있다.
편집 1:
OP가 정수 나눗셈이 아닌 임의의 숫자의 곱셈과 나눗셈을 의미할 경우 이 스레드는 사용할 수 있습니다.https://stackoverflow.com/a/12699549/1182653
편집 2:
정수 상수로 나누는 가장 빠른 방법 중 하나는 모듈식 산술과 Montgomery 감소를 이용하는 것입니다.정수를 3으로 나누는 가장 빠른 방법은 무엇일까요?
* 2 시프트 X * 2 =1비트 시프트 왼쪽 X
/ 2= 시프트 X / 2 = 1비트 시프트 오른쪽
* 3= XX * 3 = 1비트를 .
시프트와 덧셈을 사용하는 정수를 나누는 방법은 초등학교에서 배운 10진수 장수 나눗셈에서 쉽게 도출할 수 있다.각 몫 자리수는 0과 1 중 하나이므로 선택이 단순해집니다. 현재 나머지가 제수보다 크거나 같으면 부분 몫의 최하위 비트는 1입니다.
10진수 수동 나눗셈과 마찬가지로 배당금 자릿수는 가장 유의한 자릿수부터 가장 유의하지 않은 자릿수까지 한 번에 한 자리씩 고려됩니다.이것은 바이너리 나눗셈의 왼쪽 시프트에 의해서 간단하게 실현됩니다.또, 현재의 몫비트를 1 위치 왼쪽으로 이동시킨 후, 새로운 몫비트를 부가함으로써 몫비트를 수집한다.
고전적인 배열에서는 이 두 개의 왼쪽 시프트가 하나의 레지스터 쌍의 왼쪽 시프트로 결합됩니다.위쪽 절반은 현재 나머지를 보유하고 아래쪽 절반은 배당을 보유합니다.왼쪽 시프트에 의해 배당비트가 나머지 레지스터로 전송됨에 따라 하위 절반의 미사용 최하위 비트를 이용해 몫비트를 축적한다.
다음은 이 알고리즘의 x86 어셈블리 언어 및 C 구현입니다.시프트&더하기 나눗셈의 이 특정 변형을 "비실적" 변종이라고 부르기도 합니다.그 이유는 나머지가 제수(Otto Spaniol, "컴퓨터 산술: Logic and Design")보다 크거나 같지 않으면 현재 나머지에서 제수를 빼지 않기 때문입니다.치체스터:Wiley 1981, 페이지 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
- 좌회전 1위치는 2를 곱하는 것과 비슷합니다.오른쪽 이동은 2로 나누는 것과 유사합니다.
- 루프를 추가하여 곱할 수 있습니다.루프 변수와 덧셈 변수를 올바르게 선택하면 성능을 제한할 수 있습니다.그걸 다 알아봤으면 농민 곱셈을 써야지
기본적으로 기본 전력으로 곱하고 나눕니다 2
왼쪽 이동 = x * 2 ^ y
오른쪽으로 이동 = x / 2 ^ y
shl eax, 2 = 2 * 2 ^ 2 = 8
sharax, 3 = 2 / 2 ^ 3 = 1/4
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;
}
예를 들어 9와 10의 두 숫자를 1001과 1010의 2진수로 적습니다.
0의 결과 R부터 시작합니다.
숫자 중 하나(이 경우 1010)를 A라고 하고, 1을 빼고, 첫 번째 숫자를 더하면, B라고 합니다.
이제 B를 1비트 왼쪽으로 이동하고 모든 비트가 A에서 벗어날 때까지 반복합니다.
기입되어 있는 것을 보면, 무슨 일이 일어나고 있는지를 알 수 있습니다.다음은 예를 제시하겠습니다.
0
0000 0
10010 1
000000 0
1001000 1
------
1011010
여기서부터 가져갑니다.
이것은 나눗셈 전용입니다.
int add(int a, int b) {
int partialSum, carry;
do {
partialSum = a ^ b;
carry = (a & b) << 1;
a = partialSum;
b = carry;
} while (carry != 0);
return partialSum;
}
int subtract(int a, int b) {
return add(a, add(~b, 1));
}
int division(int dividend, int divisor) {
boolean negative = false;
if ((dividend & (1 << 31)) == (1 << 31)) { // Check for signed bit
negative = !negative;
dividend = add(~dividend, 1); // Negation
}
if ((divisor & (1 << 31)) == (1 << 31)) {
negative = !negative;
divisor = add(~divisor, 1); // Negation
}
int quotient = 0;
long r;
for (int i = 30; i >= 0; i = subtract(i, 1)) {
r = (divisor << i);
// Left shift divisor until it's smaller than dividend
if (r < Integer.MAX_VALUE && r >= 0) { // Avoid cases where comparison between long and int doesn't make sense
if (r <= dividend) {
quotient |= (1 << i);
dividend = subtract(dividend, (int) r);
}
}
}
if (negative) {
quotient = add(~quotient, 1);
}
return quotient;
}
이것은 곱셈에 유효합니다.
.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
아래 방법은 두 숫자가 모두 양수임을 고려한 이진수 분할의 구현입니다.뺄셈이 우려되는 경우 이진 연산자를 사용하여 구현할 수도 있습니다.
코드
-(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;
}
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"
);
이거 먹어봐.https://gist.github.com/swguru/5219592
import sys
# implement divide operation without using built-in divide operator
def divAndMod_slow(y,x, debug=0):
r = 0
while y >= x:
r += 1
y -= x
return r,y
# implement divide operation without using built-in divide operator
def divAndMod(y,x, debug=0):
## find the highest position of positive bit of the ratio
pos = -1
while y >= x:
pos += 1
x <<= 1
x >>= 1
if debug: print "y=%d, x=%d, pos=%d" % (y,x,pos)
if pos == -1:
return 0, y
r = 0
while pos >= 0:
if y >= x:
r += (1 << pos)
y -= x
if debug: print "y=%d, x=%d, r=%d, pos=%d" % (y,x,r,pos)
x >>= 1
pos -= 1
return r, y
if __name__ =="__main__":
if len(sys.argv) == 3:
y = int(sys.argv[1])
x = int(sys.argv[2])
else:
y = 313271356
x = 7
print "=== Slow Version ...."
res = divAndMod_slow( y, x)
print "%d = %d * %d + %d" % (y, x, res[0], res[1])
print "=== Fast Version ...."
res = divAndMod( y, x, debug=1)
print "%d = %d * %d + %d" % (y, x, res[0], res[1])
언급URL : https://stackoverflow.com/questions/2776211/how-can-i-multiply-and-divide-using-only-bit-shifting-and-adding
'programing' 카테고리의 다른 글
| 모델 인스턴스의 VueJs 워처와 여러 이벤트 리스너 (0) | 2022.07.16 |
|---|---|
| Chrome 확장의 공유 vuex (0) | 2022.07.16 |
| Vuex에서 여러 돌연변이를 호출하는 적절한 방법 (0) | 2022.07.16 |
| Java 실행자: 작업이 완료되었을 때 차단 없이 알림을 받으려면 어떻게 해야 합니까? (0) | 2022.07.16 |
| 불완전한 유형에 대한 참조 포인터 (0) | 2022.07.16 |