Month: February 2010

今天看到一個有趣的題目，就是計算二進位任意數值，其中包含了幾個1，這非常有趣，利用每個 bit 做&就可以解出這個問題了:

#include 
#include 
int bitcount(unsigned int);
int main(){
    int count = 0, a;
    a = 1023;
    count = bitcount(a);
    printf("%d有%d個位元為1\n\n", a, count);
    
    system("pause");
    return 0;
}
int bitcount(unsigned int n)
{
   int count = 0 ;
   while (n)
   {
      count++ ;
      n &= (n - 1) ; //關鍵演算之處
   }
   return count ;
}

關鍵解法是在 n &= (n – 1) ; 這個地方，為什麼會是這樣寫呢，大家可以想看看，為什麼要 (n-1)，其實可以帶數字進去跑看看就知道程式為什麼會這樣寫，這個 case 可以分作兩種，數值可能會有兩種狀況，一種是奇數，另一種就是偶數，8 代表 1000，9 代表 1001，最右邊 bit 是 1 代表奇數，剩下的都是偶數，拿9當例子帶入 while 迴圈試試看，首先將 count + 1，接下來 1001 會跟 1000 做相乘動作，就會變成 1000，接下來跑另一次 while 會變成 1000 & 0111 就會變成 0 了，退出 while 迴圈，所以結論是 (n -1) 的用意是去掉一個 1 位元 bit，就像 [xxxx10 … 0] -1 = [xxxx01 … 1] …. 每運算一次相乘，就會少掉一個 1，原理就是這麼簡單。 這只是一種解法，歡迎大家討論看看還有無其他方法？

最近看到網路上討論 C/C++ 題目，某公司主管給新進人員面試的 C/C++ 考題，如下：

int main(void)
{
     int *a,*b;
     a=1;
     b=1;
     printf("%d\n",a+b);
     return 0;
}

請問上面這個題目，哪裡有出問題，這是面試官問新進人員的題目之一，看也知道這程式丟到 Dev-C++ 是不會過的，*a *b 都是宣告為整數指標型態，可是在 a=1 或 b=1 在 Dev-C++ 裡面是編譯不過的，但是那寫法是沒有錯的，就像你設定 a=0 或者是 a=NULL 是一樣意思，不過最好是不要這樣寫，assignment 這樣寫不太好，可以改成 a = (int *)1; b = (int *)1; 這樣就可以順利編譯通過，再來 printf(“%d\n”,a+b); 這行錯很大，指標相加會爆炸吧，如果程式這樣寫，不把 OS 搞掛，那我還會覺得懷疑呢，正確寫法是指標加上 offset(位移)，這樣才是可以正確執行的，所以我們把程式改成下面：

int main(void)
{
     int *a,*b;
     a = (int *)1;
     b = (int *)1;
     printf("%d\n",a+(int)b);
     return 0;
}

最後的執行結果是 5，(int) b 就相當於 sizeof(*b) 也等於 sizeof(int *) 答案都是四，所以就是 1+4 =5，指標是不能相加的，只能透過 offset 方式來讓指標指向不同 base，但是如果是指標相減，那就是求 offset 的意思喔，看一下底下例子

int main(void)
{
    int *a,*b;
    a = (int *)0x5566;
    b = (int *)0x5570;
    printf("%d %d %d %d %d\n", a, b, (int)a+(int)b, a+(int)b, sizeof(int *));
    printf("%d\n", a - b);
    printf("%d\n", ((int)b - (int)a)/sizeof(int *));
    return 0;
}

要算 offset 也非常容易，只要先轉成 10 進位相減在除以 sizeof(int *) 這樣就可以求出結果了，a-b 除以四其實 -2.5 取補數，所以是 -3，如果是 b-a 就是整數3了，只是位移 3 個 bit，其實觀念就是這樣，指標位址不能相加，但是指標位址可以相減 = Offset，觀念大致上是這樣，最後補上完整程式，大家可以 run 一次看看就知道了

#include "string.h"
#include "stdlib.h"
#include "stdio.h"

int main(void)
{
    int *a, *b;
    a = (int *)1;
    b = (int *)1;
    printf("%d %d %d\n", a + (int)b, (int)(a + (int)b), (int)a + (int)b); 
    a = (int *)0x5566;
    b = (int *)0x5570;

    printf("%d %d %d %d %d\n", a, b, (int)a+(int)b, a+(int)b, sizeof(int *));
    printf("%d\n", a - b);
    printf("%d\n", ((int)b - (int)a)/sizeof(int *));
    
    a = (int*)0x1000;
    b = a + 3;
    printf("%d %d %p %p \n", a, b, a, b);
    
    system("pause");
    return 0;
}