簡學：二進制數制的應用

設現有正整數150，二進制形式為10010110，現有如下題目，求其儘可能簡單的解法。

題目一：判斷該正整數是否是2的乘方；

解法：

由上表可以看出2的乘方的二進制形式只有一個bit為1，因此判斷一個正整數A是否為2的乘方，可以判斷A&(A-1)是否等於0，若結果為0，則是2的乘方，若不為0則不是2的乘方。

題目二：判斷正整數是否能被4整除；

解法：

一個正整數可以將其表示為A=M*8+N；M是A的高位bit組成的數字，N是低三位bit組成的數字，例150=(10010)18*8+6；因為M*8是能被4整除的，因此只需判斷N能否被4整除即可，從上式可以看出150的N值不能被4整除，所以該正整數不能被4整除。

題目三：不用乘法器求該正整數*3的結果；

解法：

根據上表一個正整數A*2的結果為將該正整數的二進制左移一個bit位，並低位補0。因此求一個正整數*3的結果根據乘法的基本定律得到：A*3=A*(2+1)=A*2+A,而A*2可以轉換為左移補0的動作，因此A*3可以轉換為不用乘法器的運算。

解法：該整數的最大可能值為255，因此該整數的二進制形式可以用8個bit位表示X7X6X5X4X3X2X1X0；根據題目二的思想，可以將該整數表示為A=X7*128+X6*64+X5*32+X4*16+X3*8+X2*4+X1*2+X0；

A/7=(X7*128+X6*64+X5*32+X4*16+X3*8+X2*4+X1*2+X0)/7；

A/7=X7*(128/7)+X6*(64/7)+X5*(32/7)+X4*(16/7)+X3*(8/7)+(X2*4+X1*2+X0)/7；

根據除法的基本定律可以知道除法結果=商和餘數：

分別計算上式的元素：

根據除法的基本定律可以得出A/7：

餘P：X7*2+X6*1+X5*4+X4*2+X3*1+X2*4+X1*2+X0

=X7X6+X5X4X3+X2X1X0(P的最大值3+7+7=17)

商Q：X7*18+X6*9+X5*4+X4*2+X3*1+0

=9*X7X6+X5X4X3

由上式可以看出餘數P的最大值可能為17因此餘數P還能除以7；

因此真正的餘數和商等於：

餘：P/7取餘p；商：Q+P/7取商q

因為P的值為0-17是有限的值，因此可以枚舉求其商和餘數：

case(P)

0:q=0;p=0;

1:q=0;p=1;

2:q=0;p=2;

。。。。。

17:q=2;p=3;

得到一個0-255的未知整數除以7的最終結果：

商=Q+q=9*X7X6+X5X4X3+q；餘數=p，pq可有case(P=X7X6+X5X4X3+X2X1X0)求得，因此整個運算不需要用到除法器。