2014/4/9

計算Bits中有多少個1

  給定一個二進位數值計算有多少個1在裡面,這是很常見的演算問題也常常在面試中被問到(至少我的面試經驗就曾遇過一次),這個題目就個人觀點來看是驗證受測者是否理解Bit Operator。
  最單純的想法就是每次都檢查最低位元是否為1,是的話統計值就加1,然後把所有位元都往右移一格直到待測值變成0就可以結束了,程式碼如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int count_1_bits_method1 (unsigned int val)
{
 int cnt = 0;
 while (val) {
  if (val & 0x1)
   cnt += 1;
  val >>= 1;
 }
 
 return cnt;
}
需要注意的是參數有用unsigned作為修飾,如果這邊是用有號數作為參數作為參數會導致無窮迴圈,原因在於右移運算子(Right Shift Operator)對於有號值的負數會作負號延展(signed extention)。

  另一個想法則是把最低位元的1依序消除,直到數值裡面都沒有1為止,這步驟做多少次就表示有多少個1,這裡需要巧妙的使用算式N & (N - 1),舉例8(二進位為1000b),減1後會得到7(二進位為0111b),是否觀察到因為最低位減1不夠減了所以依序向前一位數借1,直到最低的高位元是1為止(因為夠借了不需要再往上借位),將1000b與0111b做&(And Bitwise Operator)運算後就可將最低位的1給消除了,程式碼如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int count_1_bits_method2 (int val)
{
 int cnt = 0;
 while (val) {
  cnt += 1;
  val = val & (val - 1);
 }
 
 return cnt;
}

  兩個演算方法最差的狀況所需時間都一樣,但平均而言第二種效率會好一些,會出這題目主要是想確定受測者能靈活運用位元運算子吧!?面試系統底層或是嵌入式相關工作應該會比較容易遇到這類考題。

2014/2/23

【C/C++】修飾子小細節大臭蟲

這裡要探討的是修飾子可能導致的臭蟲,很容易埋入的臭蟲而且難以找出,直接看下面這段程式:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <linux/types.h>

int main (int argc, char *argv[])
{
 __u16 b;
 __u8 a[3];
 
 b = 102;
 
 if (argc <= 1) {
  printf ("Please provide 1 integer as arguments\n");
  return -1;
 }
 
 if (sscanf (argv[1], "%d", &a[0]) != 1) {
  printf ("Wrong argument: %s\n", argv[1]);
  return -1;
 }
 
 printf ("a[0] = %d, b = %d\n", a[0], b);
}

先看執行結果:

1
2
$ ./test 10
a[0] = 10, b = 0

從程式描述可知預期輸出結果應該是b = 102
但問題在哪呢?如果有試著編譯上述程式碼還會發現編譯時,編譯器早發覺不對勁而提出警告了:

1
2
3
$ gcc -o test test.c 
test.c: In function ‘main’:
test.c:16:2: warning: format ‘%d’ expects argument of type ‘int *’, but argument 3 has type ‘__u8 *’ [-Wformat]

根據編譯器提出的警告,可以有兩種修正方法:
第一種,讓編譯器開心但會徹底把臭蟲埋入程式且難以發現:
既然編譯器預期%d修飾符應該給對應一個int *類別變數,那就改成

1
2
3
4
if (sscanf (argv[1], "%d", (int *)&a[0]) != 1) {
 printf ("Wrong argument: %s\n", argv[1]);
 return -1;
}

改完後看來編譯器滿意了,沒有丟出任何警告執行應該就沒問題吧,結果發現結局一樣,這時不禁開始懷疑sscanf這個函數是不是有bug阿?

翻閱sscanf手冊的Conversions區段有以下描述:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
Conversions
  The following type modifier characters can appear in a conversion spec‐
  ification:

  h      Indicates that the conversion will be one of d, i, o, u,  x,  X,
         or  n  and  the  next  pointer  is  a  pointer to a short int or
         unsigned short int (rather than int).

  hh     As for h, but the next pointer is a pointer to a signed char  or
         unsigned char.

還沒看出端倪嗎?沒關係,再看看下面增加幾行印出變數位址的程式內容:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
#include <linux/types.h>

int main (int argc, char *argv[])
{
 __u16 b;
 __u8 a[3];
 
 b = 102;
 
 if (argc <= 1) {
  printf ("Please provide 1 integer as arguments\n");
  return -1;
 }
 
 if (sscanf (argv[1], "%d", (int *)&a[0]) != 1) {
  printf ("Wrong argument: %s\n", argv[1]);
  return -1;
 }
 
 printf ("a[0] = %d, b = %d\n", a[0], b);
 printf ("Address of a[0]: %p\n", &a[0]);
 printf ("Address of b: %p\n", &b);
 printf ("Size of int: %d\n", sizeof (int));
}

執行結果如下:

1
2
3
4
5
$ ./test 10
a[0] = 10, b = 0
Address of a[0]: 0xbfc058cb
Address of b: 0xbfc058ce
Size of int: 4

發現變數b距離a[0]只有3 bytes,且得知在此系統環境下一個int長度是4 bytes,此時是否恍然大悟?原來sscanf使用%d修飾字要求把argv[1]字串解析成數值為int並且存入a[0],但a[0]實際只有1 bytes呢!多出來的3 bytes就把記憶體後面連續的空間也改蓋掉了,此時變數b的內容就給填為0了。

第二種修正方法:
回憶剛剛貼的手冊說明內容,既然後面承接的變數長度為8 bits,則應該將程式內容改為:

1
2
3
4
if (sscanf (argv[1], "%hhd", &a[0]) != 1) {
 printf ("Wrong argument: %s\n", argv[1]);
 return -1;
}

得到結果也符合預期且編譯器也不再哇哇叫,皆大歡喜!

Keywords: C/C++、Variable Alignment

2014/2/9

【Ubuntu】Chromium瀏覽器播放影音串流檔

因為各種影音解碼器(codecs)有版權問題,瀏覽器預設沒有帶入播放串流影音(如:mp3 stream)功能,如果需要相關串流影音必須自行另外安裝:

sudo apt-get install chromium-codecs-ffmpeg-extra
安裝完後重新啟動瀏覽器(有可能需要重新開機)就可以正常播放串流影音了。

Key Word:ubuntu, browser, chromium, stream codecs

2013/9/28

【樹莓派】遠端桌面的另一個選擇!

  除了使用Windows內建的遠端桌面連線工具可以顯示RPi桌面外,發現還有個滿不錯用的工具MobaXterm可以達到類似的功能(但需先開啟SSH連線功能),這工具整合了很多終端機連線功能,像是SSH、SSH Tunneling、Telnet...等。
  直接到下載頁面下載最新的軟體,目前最新版本是6.5。
  下載安裝後,開啟軟體點選左上角的New Session:
選擇Serial透過COM Port連線RPi:
選擇Serial Port並設定Speed為115200,其他維持預設按下OK按鈕即可:
給RPi接上電源,等系統完成初始程序即會停在登入階段,輸入帳號密碼登入,接著輸入sudo raspi-config開啟設定頁面:
選擇Advanced Options:
然後選擇SSH,將之設定為Enable即可:
確定RPi已連上網路(若需要透過Wifi連線可以參考這篇設定說明),使用ifconfig命令查詢RPi的IP位址:
再點選左上角的New Session,這次選擇SSH,在Remote Host輸入IP其他維持預設即可:
開啟連線後輸入帳號pi即可完成登入:
接著輸入命令lxsession&即可開啟遠端桌面,開一個Pi Store看看可以發現會用一個新視窗來呈現開啟的應用程式,這樣就可以在Windows工具列上看到對應的視窗!
整合度可以說是很高,但使用順暢度一樣不太好,這應該是RPi本身效能的限制吧!?

【樹莓派】硬體重置(Reset)接腳

  在Raspberry Pi Model B 2.0版新增了P6 Header可用來重置(Reset)硬體,位置在HDMI接孔的左邊有兩個接點:
Raspberry Pi, RPi
用途就跟一般電腦一樣當系統發生死當或是特殊狀況需要重啟時只要將這兩Pin做短路就會重新啟動電路,可以使用金屬鎳子或是用迴紋針接觸P6即可:
Raspberry Pi, RPi
怕短路到其他線路可以準備一個pin腳跟按鈕(可以找沒再用的電腦主機,開關按鈕或是Reset按鈕)稍微加工一下幫RPi做個Reset按鈕:

先將2 pins Header銲在RPI上:
再把按鈕插到Header上就完成了,之後如果遇到當機之類狀況就可以直接用這Reset按鈕完成重開機,不必再拔電 & 上電了

2013/9/16

【樹莓派】設定遠端桌面

  如果不想另外接螢幕或電視,又想使用桌面系統可以在網路設定好後使用遠端桌面連線來控制RPi,設定方法也很簡單,只要透握apt-get套件管理程式安裝xrdp就可以了。
  首先安裝xrdp:sudo apt-get install xrdp
  接著開啟Windows遠端桌面程式,輸入RPi IP接著點選連線即可
輸入帳號密碼後即可完成連線
感覺RPi的X-Window執行起來沒有很順暢,還是指令介面用起來比較順暢!

2013/9/15

【樹莓派】用omxplayer播放AVI檔案並支援繁體中文字幕

閒來無事跑到電子街晃了一圈發現RCA Cable還滿便宜的,就買回來試試樹莓派的影音播放功能,一條是兩端公接頭的黃色Cable,用來傳輸影像的:
另一條是3.5mm雙聲道音源轉成RCA左右聲道的Cable:
接線也很簡單,實驗板端的接法就照接頭外型對應接起來就好:
電視端則可以照顏色接起來:

  • 黃色:影像
  • 白色:左聲道
  • 紅色:右聲道

接線完成後就可以讓實驗板開機也把電視打開,可以看到電視會顯示開機過程最後跟用終端機連線一樣會停在登入畫面,但可以在螢幕左上方多看到一顆草莓XD:
接著可以選擇接鍵盤繼續操作或是透過RS232控制實驗板,接著使用omxplayer來播放影片omxplayer --subtitles test.cht.srt test.avi,影片很順利的可以播放聲音也沒有問題,但卻發現字幕是亂碼或是一堆方框...
  Google一下發現可以安裝中文字型解決字幕顯示問題,直接透過apt-get套件管理程式安裝字型套件,sudo apt-get install ttf-wqy-microhei
  接著撥放影片時直接指定顯示字型即可正確撥放影片,omxplayer --font /usr/share/fonts/truetype/wqy/wqy-microhei.ttc --subtitles test.cht.srt test.avi

PS. 使用omxplayer撥放影片不需要打開X-Window,直接透過指令帶起即可