[NKU]sweet @ Google && TopCoder && CodeForces

            BlogJava :: 首頁 :: 聯系 :: 聚合  :: 管理
            33 Posts :: 1 Stories :: 15 Comments :: 0 Trackbacks

          常用鏈接

          留言簿(2)

          我參與的團隊

          搜索

          •  

          最新評論

          閱讀排行榜

          評論排行榜

          2011年10月7日 #

          應刁哥多年前的約稿,外加結合編譯原理系列連載,整理一下上一篇文章,寫一個簡易的匯編教程……
          盡管謬誤,疏漏若干,但是本文的目的不在于培養學霸,而在于讓不會匯編的人簡單看看就能寫出個基本能用的匯編程序……
          在程序設計中,我們知道一項基本原理:語言越高級,一般來講容易編寫,形式簡潔,可移植性強,效率低……
          反過來,語言越低級,越難編寫,代碼越容易是又臭又長還看不懂,越難移植,但是效率會很高……
          匯編就是比較低級的語言了,由于其不太好移植,匯編版本又多種多樣
          因此,本著活學活用,到時候不會就查手冊的原則,本文不會太著重強調語法,語法以intel語法為主……
          Chapter1:一些基本知識
          首先,CPU有若干寄存器,在32位CPU中,形如eax,ebx,ecx,edx……64位CPU則為rax,rbx……
          雖然寄存器這個名字很NB,其實它的本質上就是int,為了向下兼容的需要,一些老的程序,也有可能能在新型的CPU上運行(詳見DOS老游戲,有的能玩,有的不能玩)
          以64位舉例:
          64位寄存器rax,低32位是eax,eax低16位是ax,ax高8位叫ah,低8位叫al……
          CPU只能直接對寄存器進行運算……因為電路結構就是那樣的……因此,所有的操作,都需要經過寄存器
          譬如賦值:A = 1,實際上是 AX = 1; A = AX; 譬如 A = A + B,應該是 AX = A; AX += B; A = AX; 這樣
          我是比較不求甚解的,99%功能(運算,判斷,指針)等,使用eax,ebx,ecx,edx都能搞定……于是咱們也就不說別的了……
          Chapter2:匯編的基本語法:
          匯編語言大概分為四個段,其中比較需要記住的就是代碼段和數據段……
          用類似高級語言的思路來講,數據段用于定義一些全局變量,代碼段用于寫程序……
          來看一個簡單的 Hello World(環境:yasm,64位)
          global main 
          extern printf 
          section .data 
          ctrlout   db      '%s', 10, 0 
          hw    db      'Hello World', 0 
          ; this is a comment
          section .text
          main:
          mov rax, 0
          mov rdi, ctrlout
          mov rsi, hw
          call printf
                  mov rax, 0
          ret
          其中,剛開始global main 表示程序入口,由于這里直接調用了Linux的函數printf,之后需要gcc編譯,所以叫做main,如果只使用中斷輸出的話,可以搞成_start
          之后extern意義和C++類似,表示這個函數在別處,叫編譯器以為他有就行……
          section .data  表示數據段,后面是一些定義,以及初始化
          注意這里定義的東西類型都像是指針一樣,ctrlout,hw 實際上是地址……
          初始化必須搞的干凈一點,有一次調了半天不對,就是因為一個64位int,前4位沒有初始化成0……
          之后 section .text 表示代碼段,這里調用C語言函數,網上說,64位匯編中,參數傳遞方式有了修改,大概是有4~5個寄存器專門保存參數,如果參數過多,再放入棧,rax存放棧中的參數個數……我們想printf("%s","Hello World"),就要調用兩個參數,于是,我們把第一個參數,字符串ctrlout的指針mov進rdi,hw mov進rsi,rax賦值為0 ,然后,調用……
          (實現時,需要手冊自行查閱一下本機怎么搞)
          函數的返回值在rax,于是return 0
          然后 yasm -f elf64 XXX.asm
          gcc -o XXX XXX.o
          ./XXX
          一個嶄新的hello world 出現了……
          Chapter3:匯編的一些簡單指令:
          由于這是速成教程,選取一部分指令……要記住,CPU只能直接對寄存器進行運算……
          mov:相當于賦值, mov eax,b  相當于eax = b;
          注意:mov 后面的兩個東西至少要有一個是寄存器……
          同時,和高級語言一樣,不能搞什么 mov 10,eax……
          add:add eax,b 相當于eax+=b
          sub:基本同上……
          mul || imul:前面是無符號的乘,后面是有符號的乘,默認被乘數在AX,于是指令形如:mul BX,如果有溢出,則高位溢出到DX,記得備份DX的東西……
          div  ||  idiv:前面是無符號整除,后面是有符號整除,默認被除數是DX(高16位)和AX(低16位),因此,除法之前記得把DX清零,否則數會不對……
          之后商在AX,余數在DX
          指令形如:div BX
          push/pop:每個程序都有棧,或者是在程序中定義堆棧段,或者使用默認棧
          push eax,表示把eax放進棧里,pop ebx,表示取出棧頂,放在ebx中……
          push和pop異常重要,一個重要作用就是保護寄存器,譬如DX中有內容,但是現在要做乘法,沒準會破壞DX(見上),于是,先PUSH DX,然后,乘法,然后POP DX,又好比你要調用一個函數,但是寄存器里有有用的信息,不保證這個函數不會破壞,于是,把所有寄存器先push進去,運行函數,然后再pop出來,這是常用技巧……
          另外也可以用來給函數傳參數,傳時倒序壓入,用時順序取出,棧,先進后出,你們懂的……
          Chapter4:if以及循環
          首先我們要記得,被Dijkstra老爺子罵的一文不值的goto……
          jmp語法和C++里的goto基本一樣
          start:
          XXX
          jmp start
          然后,匯編沒有if then,但是有條件goto
          有個語句叫做cmp
          cmp X,Y (老原則,這兩個得有一個寄存器……如果和常數比較,常數必須在后面)
          傳說中具體實現是減法……
          這個的效果是可能改變若干標識位的值……譬如:0標識,進位標識,溢出標識……等等……
          然后,有若干指令
          jl XX(l==less) 相當于 if (x<y) goto XX; 下同
          jg XX(g==greater)
          jle XX(ne==less or equal)
          jge XX(ge==greter or equal)
          jnle XX(n==no->nle==g)
          jnge XX(n==no->nge==l)
          有了if then,各種運算,我們就能做出來&&,||的邏輯
          有了if then,我們也能做出循環……
          很多的功能就有了……
          Chapter5:實戰
          看看
          int main() {
              int a,b,c;
              input(a);
              input(b);
              if (a < b) {
                  c = a;
              } else {
                  c = b;
              }
              print(c);
          }
          用匯編翻譯出來啥樣:
          global main 
          extern printf 
          extern scanf 
          section .data 
          ctrlout   db      '%lld', 10, 0 
          ctrlin    db      '%lld', 0 
          _a db 0,0,0,0,0,0,0,0
          _b db 0,0,0,0,0,0,0,0
          _c db 0,0,0,0,0,0,0,0
          section .text
          main:
          mov rax, 0
          mov rdi, ctrlin
          mov rsi, _a
          call scanf
          mov rax, 0
          mov rdi, ctrlin
          mov rsi, _b
          call scanf
          MOV rax, [_a]
          CMP rax, [_b]
          jl @0
          jmp @2
          @0:
          MOV rax, [_a]
          MOV [_c], rax
          jmp @1
          @2:
          MOV rax, [_b]
          MOV [_c], rax
          @1:
          mov rax, 0
          mov rdi, ctrlout
          mov rsi, [_c]
          call printf
          mov rax, 0
          ret
          Chapter6:其它
          由于現實生活中,我需要寫匯編時候實在是少,因此也沒啥經驗……盡管借助手冊,可以對付著寫一點匯編代碼,但是那是不科學的……對我來講,匯編告訴我們的一些底層的東西更有價值,可以在高級語言中有所體現:譬如一些表達式的寫法,可以考慮寫的更科學一些,譬如 c = a / b, q = a % b,記得寫成 c = a / b; q = a - c * b,譬如靈活使用switch,等等……
          posted @ 2012-01-26 22:42 sweetsc 閱讀(687) | 評論 (0)編輯 收藏

          最近,做OS大作業,編譯大作業,和進行實驗室工作,強烈認識到了自己對C語言的了解不多……
          于是今天老圖借了本書,學習一下……
          來看一下我最頭疼的define……
          define的作用:
          一是直接定義一個東西……類似標記
          譬如:
          1 #ifndef test
          2 #define test
          3 /*
          4 balabalabala.
          5 */
          6 #endif
          劉JX老師在大一C++課上教育我們,寫頭文件一定要加上這么個東西……為什么呢……
          再提一下include的事情…… #include<XXXX>,實際上是直接把XXXX整個文件COPY了進來……
          如果出現這樣的情況:
          1 #include <set>
          2 #include <map>
          我們知道,Cpp的 map 實際上是用 set 做的,map的頭文件里肯定有一個 #include <set>,那么,相當于set這個文件在這段程序里面出現了兩次……
          如果沒有ifndef這套的話,相當于將set中的代碼重復貼了兩次,就粗大事了……
          代碼第一段ifndef test 代表:如果沒有define test,則執行下面的那段,先 define test,然后balabala,最后endif,下次再看到這段代碼的時候,ifndef test ,此時會發現test已經define過了,直接endif,中間balabala的代碼不會重復兩次……

          二是直接定義一些……怎么說呢,類似替換規則的東西……

          譬如:直接定義常量:
          1 #define MAXN 10000
          這個實際上就是直接在程序編譯之前,將里面的MAXN都替換成10000
          預先定義一些常量,好處大家都懂:避免程序內部太多的“magic number”,增強可讀性,也便于修改……這里相當于直接替換,貌似C的數組,定義的時候不能用int做下標,const int也不行,只能通過這個方法,用立即數……

          譬如:給一些東西改個名字:
            1 #include <stdio.h> 
            2 #define Q scanf 
            3  
            4 int main() { 
            5     int a; 
            6     Q("%d",&a); 
            7     printf("%d\n",a); 
            8     return 0; 
            9 } 

          這里有一些玄機:
          1:#似乎是因為沒有轉義?所以不能胡用……
          譬如:#define USEMATH #include <math.h> 是不能達到預期效果的……
          2:如果這一行太長,可以用\表示和下一行連起來…… 貌似這個'\'也沒轉義, #define BACKSLASH \ 也是不行的……

          譬如:可以定義一些簡單的函數:
          #define max(a,b) ((a) > (b) ? (a) : (b))
          某種意義上這比template NB...
          這樣,int c = max(a,b); 就自動替換成 int c =((a) > (b) ? (a) : (b)); 了
          此處有一個技巧:有的時候,咱們需要用大括號來實現這個"函數",但是,由define直接替換知道,這個替換出來,相當于{/*balabala*/};這樣,語法是錯的……
          于是怎么辦呢……咱們可以用 do {/*balabala*/} while(0) 這樣的形式,繞開這個問題…… 在上次OS大作業上咱們都見到了……
          此處還有兩個玄機:一是千萬記得要加括號……為什么呢……
          譬如:
          #define mul(a,b) a * b
          看著挺好,mul(1,2 + 3)就出事了…… 直接替換出來,是 1 * 2 + 3,就錯了……
          正確方法是:#define mul(a,b) ((a) * (b)),萬無一失……
          另一個玄機是避免++,--之類的,譬如
          #define sqr(a) ((a) * (a))
          sqr(a++),如果sqr是真的函數的話,計算出沒有問題……但是define會忠實的給你替換成((a++) * (a++))……怎么加的不重要,結果就不是你想的了……

          最后有兩個用法,一個是#,#會將你作為“函數”的“參數”傳入的東西轉化為字符串;一個是...,作用一看便知:
           1 #include <stdio.h>
           2 #define max(a,b) ((a) > (b) ? (a) : (b))
           3 #define PRINT() printf(__VA_ARGS__)
           4 #define debug(x) do { \
           5     PRINT(#x);  \
           6     PRINT(" = %d\n",(x)); \
           7     } while (0)
           8 
           9 int main() {
          10     int a,b;
          11     scanf("%d%d",&a,&b);
          12     debug(a);
          13     debug(b);
          14     debug(a + b);
          15     debug(max(a,b));
          16     return 0;
          17 }
          posted @ 2011-12-02 01:59 sweetsc 閱讀(334) | 評論 (0)編輯 收藏

          題意很簡單……雙方給N個人(N<=6)打三國殺1V1,你知道對手每個人能克制你哪些人,我們認為兩個人對打,他能克你則他勝利,否則你勝利;某人的N個人死光就輸了……你需要組織陣容按照順序對抗對手……求有沒有一個順序,無論對手順序如何,你都能勝……
          N!枚舉自己的順序,然后N!枚舉對方的順序,O(N)驗證即可……
          注意字典序最小……

           1 #include <cstdio>
           2 #include <cstring>
           3 #include <string>
           4 #include <map>
           5 #include <algorithm>
           6 #include <iostream>
           7 
           8 using namespace std;
           9 
          10 map<string,int> mp;
          11 int n;
          12 int res[10];
          13 int my[10];
          14 char buf[50];
          15 char name[10][50];
          16 string ans;
          17 
          18 void check() {
          19     int enemy[] = {0,1,2,3,4,5,6,7,8,9};
          20     do {
          21         int i = 0;
          22         int j = 0;
          23         while (i < n && j < n) {
          24             if ((1 << my[i]) & res[enemy[j]]) i ++else j++;
          25         }
          26         if (i == n) return;
          27     } while (next_permutation(enemy,enemy + n));
          28     string tmp;
          29     for (int i = 0; i < n; i++) {
          30         if (i) tmp += " ";
          31         tmp += name[my[i]];
          32     }
          33     if (ans == "" || ans > tmp) ans = tmp;
          34 }
          35 
          36 int main() {
          37     int nn; scanf("%d",&nn);
          38     for (int ii = 1; ii <= nn; ii++) {
          39         mp.clear();
          40         memset(res,0,sizeof(res));
          41         scanf("%d",&n);
          42         for (int i = 0; i < n; i++) {
          43             scanf("%s",name[i]);
          44             mp[string(name[i])] = i;
          45         }
          46         for (int i = 0; i < n; i++) {
          47             int m; scanf("%d",&m);
          48             for (int j = 0; j < m; j++) {
          49                 scanf("%s",buf);
          50                 int tmp = mp[string(buf)];
          51                 res[i] |= 1 << tmp;
          52             }
          53         }
          54         for (int i = 0; i < n; i++) {
          55             my[i] = i;
          56         }
          57         ans = "";
          58         do {
          59             check();
          60         } while (next_permutation(my,my + n));
          61         printf("Case %d: ",ii);
          62         if (ans == "") {
          63             puts("No");
          64         } else {
          65             puts("Yes");
          66             for (int i = 0; i < ans.length(); i++) putchar(ans[i]);
          67             putchar(10);
          68         }
          69     }
          70     return 0;
          71 }
          posted @ 2011-10-07 20:15 sweetsc 閱讀(627) | 評論 (0)編輯 收藏

          主站蜘蛛池模板: 达孜县| 武川县| 静海县| 万年县| 茂名市| 郧西县| 崇明县| 武定县| 德安县| 合山市| 二手房| 土默特左旗| 澎湖县| 阳信县| 临颍县| 合江县| 普定县| 合阳县| 收藏| 忻州市| 庄河市| 繁峙县| 大同市| 叶城县| 岗巴县| 蒙城县| 尉犁县| 平原县| 维西| 从化市| 多伦县| 清镇市| 邳州市| 双桥区| 漳平市| 会同县| 合阳县| 镇宁| 图们市| 蕲春县| 合江县|