2013年1月16日 星期三

判斷n是否為2的冪次

最近看到這則程式碼
return (n!=0 && (n&(n-1)==0))
我想了一下恍然大悟
這種東西不知道原本是誰想到的


組語版 (Assembly Language Version)


#include<stdio.h>

__declspec(naked) int __stdcall Chk2Power(int num)
{
  __asm{

      pop ecx ;先將保存好返回位址

      pop eax ;抓出 num 放在 eax

      cmp eax, 0;因為 CPU 於暫存器內部比較速度快
      jz  endp  ;假如 ZF=1 則跳躍離開 (等於零嗎?)
      js  isneg ;假如 SF=1 則跳躍翻正 (是負數嗎?)
      jmp chk   ;正數直接跳至判斷區域
  isneg:
      neg eax ; 翻正
  chk:
      mov  edx, eax ;eax 扣1前先偷偷放到 edx
      dec  eax      ;用扣1專用指令 dec
      and  eax, edx ;計算 Bitwise AND
      test eax, eax ;等於零嗎 ? (測試 eax & eax)
      jnz  iszero   ;假如否, 則跳躍至 iszero 回傳零
      or   eax, 1   ;加 1
      jmp  endp     ;跳躍離開
  iszero:
      xor  eax, eax ;設定 eax = 0
  endp:
      push ecx ;回存返回位址
      ret      ;返回
  }
}

int main(int argc,char* argv[])
{
  printf("%x", Chk2Power( atol(argv[1]) ) );
  return 0;
}


我稍微修改了一些內容,cmp eax,0 的部分 改為 test eax,eax

12 則留言:

  1. 我雖然不知道起源,不過這條運算式是很有名的
    "Optimized way to check 2 power " algorithm
    我最早在 Quake 1 的原始碼裡面有看過,不過我看到的
    是嵌入式組語變種版,有興趣 夜風可以開 VC 玩玩看 結果是一樣的喔,這會用組語的原因裡面有很多 手動最佳化的細節,例如 加 1 使用 or eax, 1 用邏輯方法達成,反正夜風 看看源始碼就懂了

    原版的 Chk2Power 的註解是英文版

    #include

    __declspec(naked) int __stdcall Chk2Power(int num)
    {
    __asm pop ecx ; 先將保存好返回位址
    __asm pop eax ; 抓出 x 放在 eax

    __asm cmp eax, 0 ; 因為 CPU 於暫存器內部比較速度快
    __asm jz iszero ; 假如 ZF=0 則跳躍離開
    __asm js isneg ; 假如 SF=0 則跳躍翻正
    __asm jmp chk ; 正數直接跳至判斷區域
    isneg:
    __asm neg eax ; 翻正
    chk:
    __asm mov edx, eax ; eax 扣1前先偷偷放到 edx
    __asm dec eax ; 用扣1專用指令 dec
    __asm and eax, edx ; 計算 Bitwise AND
    __asm cmp eax, 0 ; 等於零嗎 ?
    __asm jnz iszero ; 假如否, 則跳躍至 iszero 回傳零
    __asm or eax, 1 ; 加 1

    __asm push ecx ; 回存返回位址
    __asm ret ; 返回
    iszero:
    __asm xor eax, eax ; 設定 eax = 0
    __asm push ecx ; 回存返回位址
    __asm ret ; 返回
    }

    int main(int argc,char* argv[])
    {
    printf("%x", Chk2Power( atol(argv[1]) ) );
    return 0;
    }

    回覆刪除
  2. 作者已經移除這則留言。

    回覆刪除
  3. include 裡面要 stdio.h
    不知道為什麼有角號
    在網頁上會顯示不出來
    0.0 ~~

    回覆刪除
  4. 我註解忘了改了

    抓出 x 放在 eax 要改成

    抓出 num 放在 eax

    回覆刪除
  5. 為什麼說他是變種版
    因為他多判斷負號的功能
    你輸入 256 或 -256 都可以

    回覆刪除
  6. ㄎㄎ 夜風 可以改一下這篇專欄 把我下面
    打一堆 整併到你這篇 這樣看起來 就很豐富啦
    囧 回文裡面 程式碼無法上色 好醜

    回覆刪除
  7. 其實你自己可以改 反正都有權限

    回覆刪除
  8. 只能說 Quake 創造者 John D. Carmack
    真不是人,我偷懶的話當然寫

    n = n<0 ? -n ? n ;
    return (n!=0 && (n&(n-1)==0));

    寫 C版 不是也很好嗎~~~~ 0.0b

    Carmack 那個年代電腦並不是很快
    像 or eax, 1 其實用 dec eax 也可以
    可是聰明的地方就在於他注意到了 反正上面
    一定要 0 才走這一步,所以用 1-bit 邏輯加法 OR
    直接搞定。像 js 直接判斷SF旗標跳躍也是抄捷徑

    回覆刪除
    回覆
    1. n = n<0 ? -n : n ;
      這邊要把?改成:嗎
      還是兩個問號是新用法

      刪除
    2. 哈哈 打太快 沒注意到 是我打錯啦 :P

      刪除
    3. 上色的部分我測試後,網頁上一次不能貼太多,要分批貼

      刪除
  9. 0.0 好像不能修改 博主的文章
    似乎只能觀看,我再確認看看

    回覆刪除