程序設計里，一個數除以7，不能用除法，乘法以及模運算，應該怎麼做呢？

01-02

應該是考慮位移運算，但是我沒有想到有什麼比較好的方法

int dv7(int input) { if(input&<8) { return (input+1)&>&>3; } else { return (input&>&>3) +dv7((input&>&>3)+(input7)); } }

另外增加一個求餘數的。

int rm7(int input) { if(input&<8) { return (input==7)?0:input; } else { return rm7((input&>&>3)+(input7)); } }

這裡簡單的解釋一下吧，當前限定為非負整數，下面不再贅述。

如果a=8*b+c 其中c小於8 ，則a/7=b+(b+c)/7，這個式子就是整個的遞歸體。根據整數的二進位表示，我們可以這樣得到b,c b=a&>&>3, c=a7。

諸如此類的二進位位操作技巧在Hacker"s Delight 這本書中有非常多，在TAOCP 4A中也有提及相關技巧，本題只是最基礎的一種。

ps Hacker"s Delight 已有中文版，叫做演算法心得，有興趣的可以去看一下。

最後，抄一段hacker"s delight 裡面的答案。

unsigned divu7(unsigned n) { unsigned q, r; q = (n &>&> 1) + (n &>&> 4); q = q + (q &>&> 6); q = q + (q &>&> 12) + (q &>&> 24); q = q &>&> 2; r = n - (q &<&< 2) - (q &<&< 1) - q; return q + ((r + 1) &>&> 3); }

if D == 0 then error(DivisionByZeroException) end Q = 0 -- 將商和餘數初始化為 0 R = 0 for i = n-1...0 do -- n 是被除數 N 的位數 R = R &<&< 1 -- 將餘數左移一位 R(0) = N(i) -- 將餘數的最低位設置成被除數的當前位 if R &>= D then R = R - D Q(i) = 1 end end

這個是長除法的二進位版本。由於被除數的維數是固定的，因此它可以用電路實現。

樓主你滿意了嗎？

我本來考慮的是直接用/8去做。。然後那樣是不行的。。

但是如果以可以用乘法的話其實可以有逆元的做法。。

然後嘛。。其實還是/8然後補位。。於是我找到了這個

Bit Twiddling Hacks

我想這是你要的東西了

// The following is for a word size of 32 bits!


static const unsigned int M[] =

{

  0x00000000, 0x55555555, 0x33333333, 0xc71c71c7,

  0x0f0f0f0f, 0xc1f07c1f, 0x3f03f03f, 0xf01fc07f,

  0x00ff00ff, 0x07fc01ff, 0x3ff003ff, 0xffc007ff,

  0xff000fff, 0xfc001fff, 0xf0003fff, 0xc0007fff,

  0x0000ffff, 0x0001ffff, 0x0003ffff, 0x0007ffff,

  0x000fffff, 0x001fffff, 0x003fffff, 0x007fffff,

  0x00ffffff, 0x01ffffff, 0x03ffffff, 0x07ffffff,

  0x0fffffff, 0x1fffffff, 0x3fffffff, 0x7fffffff

};
static const unsigned int Q[][6] =

{

  { 0,  0,  0,  0,  0,  0}, {16,  8,  4,  2,  1,  1}, {16,  8,  4,  2,  2,  2},

  {15,  6,  3,  3,  3,  3}, {16,  8,  4,  4,  4,  4}, {15,  5,  5,  5,  5,  5},

  {12,  6,  6,  6 , 6,  6}, {14,  7,  7,  7,  7,  7}, {16,  8,  8,  8,  8,  8},

  { 9,  9,  9,  9,  9,  9}, {10, 10, 10, 10, 10, 10}, {11, 11, 11, 11, 11, 11},

  {12, 12, 12, 12, 12, 12}, {13, 13, 13, 13, 13, 13}, {14, 14, 14, 14, 14, 14},

  {15, 15, 15, 15, 15, 15}, {16, 16, 16, 16, 16, 16}, {17, 17, 17, 17, 17, 17},

  {18, 18, 18, 18, 18, 18}, {19, 19, 19, 19, 19, 19}, {20, 20, 20, 20, 20, 20},

  {21, 21, 21, 21, 21, 21}, {22, 22, 22, 22, 22, 22}, {23, 23, 23, 23, 23, 23},

  {24, 24, 24, 24, 24, 24}, {25, 25, 25, 25, 25, 25}, {26, 26, 26, 26, 26, 26},

  {27, 27, 27, 27, 27, 27}, {28, 28, 28, 28, 28, 28}, {29, 29, 29, 29, 29, 29},

  {30, 30, 30, 30, 30, 30}, {31, 31, 31, 31, 31, 31}

};
static const unsigned int R[][6] =

{

  {0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000},

  {0x0000ffff, 0x000000ff, 0x0000000f, 0x00000003, 0x00000001, 0x00000001},

  {0x0000ffff, 0x000000ff, 0x0000000f, 0x00000003, 0x00000003, 0x00000003},

  {0x00007fff, 0x0000003f, 0x00000007, 0x00000007, 0x00000007, 0x00000007},

  {0x0000ffff, 0x000000ff, 0x0000000f, 0x0000000f, 0x0000000f, 0x0000000f},

  {0x00007fff, 0x0000001f, 0x0000001f, 0x0000001f, 0x0000001f, 0x0000001f},

  {0x00000fff, 0x0000003f, 0x0000003f, 0x0000003f, 0x0000003f, 0x0000003f},

  {0x00003fff, 0x0000007f, 0x0000007f, 0x0000007f, 0x0000007f, 0x0000007f},

  {0x0000ffff, 0x000000ff, 0x000000ff, 0x000000ff, 0x000000ff, 0x000000ff},

  {0x000001ff, 0x000001ff, 0x000001ff, 0x000001ff, 0x000001ff, 0x000001ff},

  {0x000003ff, 0x000003ff, 0x000003ff, 0x000003ff, 0x000003ff, 0x000003ff},

  {0x000007ff, 0x000007ff, 0x000007ff, 0x000007ff, 0x000007ff, 0x000007ff},

  {0x00000fff, 0x00000fff, 0x00000fff, 0x00000fff, 0x00000fff, 0x00000fff},

  {0x00001fff, 0x00001fff, 0x00001fff, 0x00001fff, 0x00001fff, 0x00001fff},

  {0x00003fff, 0x00003fff, 0x00003fff, 0x00003fff, 0x00003fff, 0x00003fff},

  {0x00007fff, 0x00007fff, 0x00007fff, 0x00007fff, 0x00007fff, 0x00007fff},

  {0x0000ffff, 0x0000ffff, 0x0000ffff, 0x0000ffff, 0x0000ffff, 0x0000ffff},

  {0x0001ffff, 0x0001ffff, 0x0001ffff, 0x0001ffff, 0x0001ffff, 0x0001ffff},

  {0x0003ffff, 0x0003ffff, 0x0003ffff, 0x0003ffff, 0x0003ffff, 0x0003ffff},

  {0x0007ffff, 0x0007ffff, 0x0007ffff, 0x0007ffff, 0x0007ffff, 0x0007ffff},

  {0x000fffff, 0x000fffff, 0x000fffff, 0x000fffff, 0x000fffff, 0x000fffff},

  {0x001fffff, 0x001fffff, 0x001fffff, 0x001fffff, 0x001fffff, 0x001fffff},

  {0x003fffff, 0x003fffff, 0x003fffff, 0x003fffff, 0x003fffff, 0x003fffff},

  {0x007fffff, 0x007fffff, 0x007fffff, 0x007fffff, 0x007fffff, 0x007fffff},

  {0x00ffffff, 0x00ffffff, 0x00ffffff, 0x00ffffff, 0x00ffffff, 0x00ffffff},

  {0x01ffffff, 0x01ffffff, 0x01ffffff, 0x01ffffff, 0x01ffffff, 0x01ffffff},

  {0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff},

  {0x07ffffff, 0x07ffffff, 0x07ffffff, 0x07ffffff, 0x07ffffff, 0x07ffffff},

  {0x0fffffff, 0x0fffffff, 0x0fffffff, 0x0fffffff, 0x0fffffff, 0x0fffffff},

  {0x1fffffff, 0x1fffffff, 0x1fffffff, 0x1fffffff, 0x1fffffff, 0x1fffffff},

  {0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff},

  {0x7fffffff, 0x7fffffff, 0x7fffffff, 0x7fffffff, 0x7fffffff, 0x7fffffff}

};
unsigned int n;       // numerator

const unsigned int s; // s &> 0

const unsigned int d = (1 &<&< s) - 1; // so d is either 1, 3, 7, 15, 31, ...).
unsigned int m;       // n % d goes here.

m = (n  M[s]) + ((n &>&> s)  M[s]);

for (const unsigned int * q = Q[s][0], * r = R[s][0]; m &> d; q++, r++) { m = (m &>&> *q) + (m *r); } m = m == d ? 0 : m; // OR, less portably: m = m -((signed)(m - d) &>&> s);

類似verilog寫個除法器？

我印象小時候速算時，7的倍數有個有趣的規律。

等我今晚推導完或者查查資料再來填坑。

挺簡單的，推完了。

把兩位數以上的數字A=10m+n

if A==7a

then

A -7m=7b=3m+n =B

為了讓數字變小，應有減法

7(a-3b)=A-3B=m-2n

舉個栗子：5677 -&> 567-7*2=553 -&> 55-3*2=49

那麼模怎麼辦呢？

5678 -&> 557-8*2=541 -&> 54-1*2=52 -&>5-2*2=1

這是巧合嗎？我再想想。

63753-&>6375-6=6369-&>636-18=618-&>61-16=45…3

咦？不對了。

看來缺一個修補演算法，我再想想

對差余處理，感覺比較麻煩，我餓了。

於是，我想到了一個很粗暴的方法。

for(i=0；s！==0；i++)

{

s=depart(A)；//反覆迭代m-2n

A++；

}

最後餘數就是i~

放心，i但總之這樣會快多了~

ps，轉了一圈上面的答案，我覺得我的辦法好~

爪機編輯這麼拼，不贊很受傷啊喂

解釋一下黃尼瑪的答案：

剛才那個證明太蠢了……重新編輯一下：

設有帶余除法 $x = b * 2^n + r,$ 兩邊除 $m = 2^n - 1$ 即得： $x/m = (b*m + b + r)/m = b + (b+r)/m$ ，這就是用到的遞歸式。

把他的代碼壓成一行吧，我喜歡對包含尾遞歸的短代碼這麼干（類似地還有gcd等等）：

int div7(int x){return x&<=7 ? ((x+1)&>&>3) : (x&>&>3) +div7((x&>&>3)+(x7));}

另外補充一個求餘數的演算法（未測試，不保證正確性，錯了別打我。僅對非負整數適用。）：

int mod7(int x){return x&<=7 ? (x&<7?x:0) : mod7((x&>&>3) + (x7));}

它的原理是：

設有帶余除法 $x = b * 2^n + r,$ 兩邊模 $m = 2^n - 1$ 即得： $x equiv b+r ;( ext{mod}; m)$ 。

事實上，這是檢驗梅森素數時常用的技巧。

============================ FBI Warning ===============================

不要一味用追求位運算優化，可讀性是第一要義。我不認為以上兩個函數會比 x/7 或者 x%7 快。要！相！信！編！譯！器！

只使用減法就可以了。

循環減法，每次減7，知道不夠減為止，減得次數就是結果的整數部分，剩下的就是餘數。

任何整數除以7個很有意思的特性，就是小數部分是固定的六種答案，也就是所謂的無限循環小數。知道餘數了，就可以通過餘數得知是那種循環方式，從而算出小數點後的任意精確位數了。。。

這種附加無理限制條件的問題的意義是什麼？

寫個ALU吧

利用迭代法可求：我說一個思路給你

*被除數為x，除數為y，商為q，餘數為r.

根據商和餘數的關係：x=q*y+r
令餘數r的初值為被除數x，商的初值q為0
不斷從r中減去餘數y，直到無法從r中減去y為止，每減一次q加一
r的值不斷減小，q的值不斷增大，當r比被除數y小時即停止運算，q和r即為所求

如果記得沒錯的話CSAPP上有一個類似的練習題。。。所以還是要多看書～

設被除數A＝7778的整數位數為N位，N＞2 N＝4

A的首位數為a＝7

計算A－a×7×14×10∧（N－3）＝B＝918

B的整數位為M位，M＝3

B的首位數為b＝9

計算B－b×7×14×10∧（M－3）＝C＝36

以此類推，直至N小於3，查表得出結果

leetcode 上有類似的題，不過是m除以n。歸類在了binary search。

彙編語言就有這類情況。做法就是循環用減法，記錄循環次數，直到被減數做下一次減法時小於0。這時候商和餘數就都出來了。

多說一句，這就是除法的本質。所以為什麼0作為除數得到的是Inf。

循環減法或者循環bitwise

用加減實現乘除取余方法

剛做了這題。

log(32)複雜度的代碼。不使用除法、乘法、mod。主要使用移位操作。溢出返回INT32_MAX。特別注意dividend為INT32_MIN, divisor為1的情況。

// should pay a great attension to INT32_MIN.

// -INT32_MIN is useless.

//這裡需要特別注意 INT32_MIN，對於 INT32_MIN來說，取對應的正數是沒用的。當返回值為 INT32_MIN時，也是一樣。

int divide(int dividend, int divisor) {

if(divisor==0) return INT32_MAX;

if(dividend==INT32_MIN divisor==-1) return INT32_MAX;

bool flag = true;

if((dividend&>0 divisor&<0) || (dividend&<0 divisor&>0)){

flag = false;

}

// should be long ,should not use abs.

long ldividend = dividend&<0 ? -(long)dividend : dividend;

long ldivisor = divisor&<0? -(long)divisor: divisor;

if(ldivisor&>ldividend) return 0;

// should be long

long ret = 0;

int start = 0, end = 30;

while(start&<=end){

int mid = (end+start)/2;

if(((long)(ldivisor&<&ldividend){

end = mid-1;

} else {

ldividend = ldividend - (ldivisor&<&

ret = ret + (1&<&

}

return flag ? (int)ret : (int)-ret;

}

2016.9.1

數電

只要加法就能實現所有運算了，cs必修課程計算機系統組成原理中有詳細描述。

實際上面試官是想讓你寫個二分法。給定數n，求n/7，那麼倒過來看，求一個數，使得這個數的7倍大於或者等於n，小於n+1. 對於一個數加7次相當於乘7。用二分法，搜索區間為0到n。每次都比較中間值的7倍和n的大小。當然7倍你可以這麼寫：m&<&<2+m&<&<1+m. 搜索的同時記錄區間的開頭結尾。樓主無慮，不用存O（n）的數組or表什麼的。代碼略。時間複雜度是O(logn),空間複雜度是O(1). 當時在美團面試的時候被問道過類似的問題。當然最蠢笨的方法就是票數最高的那位，但是實際上任何數都可以表示成二進位的形式。