[問題] 這題C語言的原理是什麼?

[qazkevin (Linus)]

各位C哥好~想請教這段程式碼

#include <stdlib.h>
int isMultN(unsigned int n) {
    int odd_c = 0, even_c = 0; /* variables to count odd and even SET bits */

    if (n == 0)    // return true if difference is 0.
        return 1;
    if (n == 1)    // return false if the difference is not 0.
        return 0;

    while (n) {
        if (n & 1)   // odd bit is SET, increment odd_C
            odd_c++;
        n >>= 1;

        if (n & 1)   // even bit is SET, increment even_c
            even_c++;
        n = n >> 1;
    }

    /* Recursive call till you get 0/1 */
    return(isMultN(abs(odd_c - even_c)));
}

這題是在jserv課程看到的題目，
題目為: 其作用為檢查輸入整數是否為 N 的倍數，那麼 N 為多少？
我有試著執行這個程式碼，答案為檢查3的倍數。
但知道歸知道，看完這段程式碼坦白說我不明白為什麼他是在檢查3的倍數，
想請問各位大大能否給我一些方向或者提示，
我該往什麼方面去搜尋資料才能知道這個程式碼的原理?
目前看完程式碼的理解是在while迴圈裡面去計算奇數位與偶數位總共有幾個bit是1
例如: 1011
odd_c為1+0=1
even_c為1+1=2
最後用遞迴來確認回傳0 or 1
小弟看懂實作內容卻不懂原理為何?
可以請各位大大為小弟解惑嗎
感激不盡

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.161.154.5
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1528126677.A.69B.html
推 chuegou: 這應該是數學？
推 zxkyjimmy: 如同十進位數字的奇數位和跟偶數位和的差異可以用來檢
→ zxkyjimmy: 查11的倍數一樣，在二進位中可以用來檢查3的倍數
推 ckc1ark: 2^even≡3k+1,2^odd≡3k-1所以 n=3k+(#even)-(#odd)
→ qazkevin: 感謝以上大大!!!小弟明白了!!!只能說小弟數學太差了...
推 cutekid: 推 ckclark 大解釋
→ share5566: 請問2^even≡3k+1這件事情是必須要先知道才能解題嗎？
→ share5566: 還是累積足夠經驗後，足以依靠靈感推理出來呢？ 謝謝
推 LPH66: 跟靈感什麼無關, 這就只是數學而已