2의 제곱을 사용하지 않는 비트 시프트 곱셈

Question

어떻게 비트 시프트를 사용하여 36 배까지 곱셈을 수행 할 수 있습니까? 2의 제곱으로 곱하는 것이 가능하지 않습니까? 예 :

unsigned x = 4; // binary 00000000 00000000 00000000 00001000 
unsigned y = x << 3; // multiply by 8, resulting in binary 00000000 ... 00100000 

감사합니다.

Answer 1

당신은 2의 비 파워를 곱 수 없습니다

혼자 비트 시프 팅.

하지만 당신은 덧셈과 곱셈을 사용하여 분해 할 수는 :

x * 36 = x * (32 + 4) 
     = (x * 32) + (x * 4) 

32 이후 및 4는 2 (각각 2^5 및 2^2)의 힘, 당신은 별도의 변화로 사람들을 수행하고 그 결과를 추가 할 수 있습니다.

Answer 2

비트 시프트만으로는 작업을 수행 할 수 없습니다. 이진수의 비트 시프 팅은 말한 것과 똑같이 2의 제곱으로 곱하거나 나눕니다. 마찬가지로 10 진수를 10의 제곱으로 십진법으로 나눕니다 (예 : 3은 30, 300, 0.3 또는 0.03이 될 수 있지만 0.02 또는 99는 될 수 없음).

---

그러나 36을 2의 제곱으로 나눌 수 있습니다.

즉, 36을 32 + 4 (2^5 + 2^2)로 나눌 수 있습니다. 당신이 사용한 코드 ("교대를 사용하는 코드 작성")에 의해서만, 유일한 요구 사항은 비트 이동을 사용하는 것이며이 요구 사항이 충족되는 한 추가 작업을 수행 할 수 있어야합니다. 이다

, 이러한 이해와

x * 36 = x * (32 + 4) = 32x + 4x = (2^5)x + (2^2)x = (x << 5) + (x << 2) 

은 간단한 구현은 다음 두 이동 값을 추가하는 것입니다 :

int result = (x << 5) + (x << 2);