• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            A Za, A Za, Fighting...

            堅信:勤能補拙

            題目來源: http://zhedahht.blog.163.com/blog/static/25411174201142733927831/

            題目:輸入一棵二叉樹的根結點,判斷該樹是不是平衡二叉樹。如果某二叉樹中任意結點的左右子樹的深度相差不超過1,那么它就是一棵平衡二叉樹。

            #include<stdio.h>
            #include
            <stdlib.h>
            #include
            <string.h>
            #define MAX(a, b) ((a)>(b) ? (a) : (b))
            #define ABS(x) ((x)>=0 ? (x) : ((x)*(-1)))

            struct Node {
                
            void *data;
                
            struct Node *left, *right;
            };

            int
            depth(
            struct Node *root)
            {
                
            if(root == NULL)
                    
            return 0;

                
            int ldepth = depth(root->left);
                
            int rdepth = depth(root->right);

                
            return MAX(ldepth, rdepth) + 1;
            }

            int
            btree_isbalanced_naive(
            struct Node *root) /* return 1 if balanced, or return 0 */
            {
                
            if(root == NULL)
                    
            return 1;

                
            int ldepth = depth(root->left);
                
            int rdepth = depth(root->right);
                
            int diff = ldepth - rdepth;
                
            if(ABS(diff) > 1)
                    
            return 0;

                
            return (btree_isbalanced_naive(root->left) && btree_isbalanced_naive(root->right));
            }

            int
            btree_isbalanced(
            struct Node *root, int *depth)
            {
                
            if(root == NULL) {
                    
            *depth = 0;
                    
            return 1;
                }

                
            int ldepth, rdepth, diff;
                
            if(!btree_isbalanced(root->left, &ldepth) || !btree_isbalanced(root->right, &rdepth))
                    
            return 0;

                
            *depth = MAX(ldepth, rdepth) + 1;
                diff 
            = ldepth - rdepth;
                
            return (ABS(diff)<=1 ? 1 : 0);
            }

            int
            main(
            int argc, char **argv)
            {
                
            struct Node a = {NULL, NULL, NULL};
                
            struct Node b = {NULL, NULL, NULL};
                
            struct Node c = {NULL, NULL ,NULL};
                
            struct Node d = {NULL, &b, NULL};
                
            struct Node e = {NULL, &a, &d};
                
            struct Node f = {NULL, NULL, NULL};
                
            struct Node g = {NULL, &e, &f};

                
            int ret1 = btree_isbalanced_naive(&g);
                printf(
            "%s\n", ret1 ? "YES" : "NO");

                
            int dpth = 0;
                
            int ret2 = btree_isbalanced(&g, &dpth);
                printf(
            "%s : %d\n", ret2 ? "YES" : "NO", dpth);
                
            return 0;
            }

             



            posted @ 2011-05-31 16:58 simplyzhao 閱讀(393) | 評論 (0)編輯 收藏
            題目出處: http://zhedahht.blog.163.com/blog/static/25411174200712895228171/

            題目:定義棧的數據結構,要求添加一個min函數,能夠得到棧的最小元素。要求函數minpush以及pop的時間復雜度都是O(1)
            #include "StackWithMin.h"
            #include
            <cstdio>
            #include
            <cstdlib>
            #include
            <cstring>

            const int StackWithMin::MAX_SIZE ;

            StackWithMin::StackWithMin() :
                top_index(
            -1), min_index(-1)
            {
                printf(
            "StackWithMin Constructor\n");
            }

            StackWithMin::
            ~StackWithMin()
            {
                printf(
            "StackWithMin Destructor\n");
            }

            int
            StackWithMin::top() 
            const
            {
                
            if(top_index == -1) {
                    printf(
            "top() failed: Stack Empty\n");
                    
            return -1;
                }

                
            return stack[top_index]; 
            }

            int
            StackWithMin::get_min() 
            const
            {
                
            if(min_index == -1) {
                    printf(
            "get_min() failed: Stack Empty\n");
                    
            return -1;
                }

                
            return stack[min_index];
            }

            void
            StackWithMin::push(
            int value)
            {
                
            if(top_index == -1) { /* stack empty */
                    stack[
            ++top_index] = value;
                    min_index 
            = top_index;
                    
            return;
                }
                stack[
            ++top_index] = value;
                
            if(value < stack[min_index]) {
                    index[top_index] 
            = min_index;
                    min_index 
            = top_index;
                }
            }

            int
            StackWithMin::pop()
            {
                
            if(top_index == -1) {
                    printf(
            "pop() failed: Stack Empty\n");
                    
            return -1;
                }
                
            int ret = stack[top_index];
                
            if(min_index == top_index)
                    min_index 
            = index[top_index];
                
            --top_index;
                
            return ret;
            }



            class StackWithMin
            {
                public:
                    StackWithMin();
                    ~StackWithMin();
                    int get_min() const;
                    int top() const;
                    void push(int value);
                    int pop();      
                private:
                    static const int MAX_SIZE = 101;
                    int top_index, min_index;
                    int stack[MAX_SIZE];
                    int index[MAX_SIZE];
            };









            posted @ 2011-05-25 15:49 simplyzhao 閱讀(257) | 評論 (0)編輯 收藏
            當注釋掉大塊代碼時,使用"#if 0"比使用"/**/"要好,因為用"/**/"做大段的注釋要防止被注釋掉的代碼中有嵌套的"/**/",這會導致注釋掉的代碼區域不是你想要的范圍,當被注釋掉的代碼很大時容易出現這種情況,特別是過一段時間后又修改該處代碼時更是如此。

              在這里順便對條件編譯(#ifdef, #else, #endif, #if等)進行說明。以下分3種情況:

              1. 情況1:
              #ifdef _XXXX
                  ...程序段1...
              #else
                  ...程序段2...
              #endif
              這表明如果標識符_XXXX已被#define命令定義過則對程序段1進行編譯;否則對程序段2進行編譯。

              2:情況2:
              #ifndef _XXXX
                  ...程序段1...
              #else
                  ...程序段2...
              #endif
              這里使用了#ifndef,表示的是if not def。當然是和#ifdef相反的狀況(如果沒有定義了標識符_XXXX,那么執行程序段1,否則執行程序段2)。

              3:情況3:
              #if 常量
                  ...程序段1...
                  #else
                  ...程序段2...
              #endif
              這里表示,如果常量為真(非0,隨便什么數字,只要不是0),就執行程序段1,否則執行程序段2。

            posted @ 2011-05-24 15:24 simplyzhao 閱讀(525) | 評論 (0)編輯 收藏

            C++中的operator new與new operator,看上去挺像的兩姐妹,卻有天壤之別。

            operator new

            (1) 只分配所要求的空間,不調用相關對象的構造函數。當無法滿足所要求分配的空間時,則

                    ->如果有new_handler,則調用new_handler,否則

                    ->如果沒要求不拋出異常(以nothrow參數表達),則執行bad_alloc異常,否則

                    ->返回0

            (2) 可以被重載

            (3) 重載時,返回類型必須聲明為void*

            (4) 重載時,第一個參數類型必須為表達要求分配空間的大小(字節),類型為size_t

            (5) 重載時,可以帶其它參數

            new operator

            (1) 調用operator new分配足夠的空間,并調用相關對象的構造函數

            (2) 不可以被重載

            相應地,operator delete與delete operator有相似的特性。

            舉個例子

            class X
            {
            public:
            …………
                static void* operator new(size_t size)
            {
                return ::operator new(size);
            }
            static void operator delete(void* pointee)
            {
                ::operator delete(pointee);
            }
            …………
            };
            X* px = new X();

            該行代碼中的new為new operator,它將調用類X中的operator new,為該類的對象分配空間,然后調用當前實例的構造函數。

            delete px;

            該行代碼中的delete為delete operator,它將調用該實例的析構函數,然后調用類X中的operator delete,以釋放該實例占用的空間。

            new operator與delete operator的行為是不能夠也不應該被改變,這是C++標準作出的承諾。而operator new與operator delete和C語言中的malloc與free對應,只負責分配及釋放空間。但使用operator new分配的空間必須使用operator delete來釋放,而不能使用free,因為它們對內存使用的登記方式不同。反過來亦是一樣。

            你可以重載operator new和operator delete以實現對內存管理的不同要求,但你不能重載new operator或delete operator以改變它們的行為。

            當重載operator new時,可以提供更多的參數,在new一個對象時,通過在關鍵字new后的括號傳遞額外的參數。比如以下的類

            class A
            {
            public:
                …………
                static void* operator new(size_t size, const string& example)
            {
                cout << example << endl;
                return ::operator new(size);
            }
            …………
            };
            A* pa = new (“This will be printed out in operator new”) A();

            新標準的C++允許以這樣的方式傳遞一個名為nothrow的參數,以表明當為該對象分配空間失敗時,不拋出異常,而是返回0,以兼容舊標準new的行為。比如

            class B {};
            B* pb = new (nothrow) B();

            當然這只能對那些使用默認operator new操作符的類。對已經重載了operator new的類(比如上面的X和A),如果不聲明能接受nothrow參數,自然無法享受C++標準帶來的禮物。

            --------

            我們經常看到這么一句話: operator new 可以重載, placement new 不可重載。其實此處所說的不可重載應該是指全局的 placement new 不可重載,對于類域中的 placement new 是可以重載的,而且只要重載了任何一種形式的 operator new 都應該順便重載 placement new , 即 void * operator new(std::size_t count, void *ptr) 。

            操作符重載一般用于特定類型,名字解析過程同一般的函數重載。 Operator new 由于其特殊性,編譯器提供了默認提供 6 種全局重載形式,同時還允許用戶提供自定義的全局 operator new ,其參數甚至可以和全局版本一樣,除全局 placement new 外。對于類域,任何形式的 new 都是可以重載的,包括 placement new 形式。

             

            全局的 operator new( 函數 ) 有六種重載形式

            void *operator new(std::size_t count)

                throw(std::bad_alloc);           // 一般的版本

             

            void *operator new(std::size_t count,   // 兼容早版本的 new

                const std::nothrow_t&) throw();   // 內存分配失敗不會拋出異常

             

            void *operator new(std::size_t count, void *ptr) throw();  //placement 版本

                                                  

            void *operator new[](std::size_t count)  //

                throw(std::bad_alloc);

             

            void *operator new[](std::size_t count,  //

                const std::nothrow_t&) throw();

             

            void *operator new[](std::size_t count, void *ptr) throw();

             

            重載 operator new 規則

            重載 operator new 的參數個數是可以任意的 , 只需要保證第一個參數為 size_t, 返回類型為 void * 即可 , 而且其重載的參數類型也不必包含自定義類型 . 更一般的說 , operator new 的重載更像是一個函數的重載 , 而不是一個操作符的重載 . 如:

             

            全局重載示例:

            void* operator new(size_t size)  // 重載成功

            {

               printf("global new\n");

               return malloc(size);

               //return ::operator new(size);  // 遞歸調用提示 (warning)

            }

             

            //void *operator new(std::size_t size, void *ptr) // 無法重載

            //{

            //     printf("global new\n");

            //     return ::operator new(size,ptr);

            //}

             

            void * operator new(size_t size, const std::nothrow_t& e) // 重載成功 , 遞歸調用提示 (warning)

            {

                   printf("global new\n");

                   return ::operator new(size, e);

            }

             

            一般形式的 operator new 重載示例:

            void * operator new(size_t size, int x, int y, int z)

            {

                ...

            }

            X * pX = new (1, 2, 3) X;

             

            char data[1000][sizeof(foo)];

            inline void* operator new(size_t size, int n)

            {

                    return data[n];

            }

            就可以使用這樣有趣的語法來創建對象 :

            foo *p=new(6) foo(); // 把對象創建在 data 的第六個單元上  

            posted @ 2011-05-24 14:12 simplyzhao 閱讀(461) | 評論 (0)編輯 收藏
            題目出處: http://zhedahht.blog.163.com/

            題目:輸入一棵二元查找樹,將該二元查找樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點,只調整指針的指向。

              比如將二元查找樹
               
                                                    10
                                                      /    \
                                                    6       14
                                                  /  \     /  \
                                                4     8  12    16
            轉換成雙向鏈表

            4=6=8=10=12=14=16


            思路:遞歸,在一時找不到遞歸的靈感的時候,多考慮考慮遞歸的參數,有時更重要的是考慮遞歸的返回值
                  每處理一個節點,首先獲取左子樹和右子樹所返回的鏈表,然后拼接

            代碼:
            #include<stdio.h>
            #include
            <string.h>
            #include
            <stdlib.h>

            /* Problem: Convert a binary search tree into a sorted linkedlist */
            /* When it comes to Tree-Structure, recursion is always the most common solution.
               When designing recursion solution, should consider:
                   1. the parameters
                   2(important). the return object
            */

            struct Node {
                
            int value;
                
            struct Node *left;
                
            struct Node *right;
            };

            struct Node *
            BTree2List(
            struct Node *root)
            {
                
            if(root == NULL)
                    
            return NULL;
                
            struct Node *ret = NULL;

                
            /* Convert the left tree into a sorted linkedlist */
                
            struct Node *l_linkedlist = BTree2List(root->left);
                ret 
            = l_linkedlist==NULL ? root : l_linkedlist;

                
            /* Convert the right tree into a sorted linkedlist */
                
            struct Node *r_linkedlist = BTree2List(root->right);
                
            while(l_linkedlist && l_linkedlist->right)
                    l_linkedlist 
            = l_linkedlist->right;

                
            /* Combine */
                
            if(l_linkedlist)
                    l_linkedlist
            ->right = root;
                root
            ->left = l_linkedlist;
                root
            ->right = r_linkedlist;
                
            if(r_linkedlist)
                    r_linkedlist
            ->left = root;
                
                
            return ret;
            }

            int main(int argc, char** argv)
            {
                
            struct Node a = {4, NULL, NULL};
                
            struct Node b = {8, NULL, NULL};
                
            struct Node c = {12, NULL, NULL};
                
            struct Node d = {16, NULL, NULL};
                
            struct Node e = {6, NULL, &b};
                
            struct Node f = {14&c, NULL};
                
            struct Node g = {10&e, &f};

                
            struct Node *ret = BTree2List(&g);
                
            while(ret && ret->right) {
                    ret 
            = ret->right;
                }

                
            while(ret) {
                    printf(
            "%d\n", ret->value);
                    ret 
            = ret->left;
                }

                
            return 0;
            }


            posted @ 2011-05-23 09:09 simplyzhao 閱讀(380) | 評論 (0)編輯 收藏

            時常在cpp的代碼之中看到這樣的代碼:

            #ifdef __cplusplus
            extern "C" {
            #endif

            //一段代碼

            #ifdef __cplusplus
            }
            #endif
              這樣的代碼到底是什么意思呢?首先,__cplusplus是cpp中的自定義宏,那么定義了這個宏的話表示這是一段cpp的代碼,也就是說,上面的代碼的含義是:如果這是一段cpp的代碼,那么加入extern "C"{和}處理其中的代碼。

              要明白為何使用extern "C",還得從cpp中對函數的重載處理開始說起。在c++中,為了支持重載機制,在編譯生成的匯編碼中,要對函數的名字進行一些處理,加入比如函數的返回類型等等.而在C中,只是簡單的函數名字而已,不會加入其他的信息.也就是說:C++和C對產生的函數名字的處理是不一樣的.

              比如下面的一段簡單的函數,我們看看加入和不加入extern "C"產生的匯編代碼都有哪些變化:

            int f(void)
            {
            return 1;
            }
              在加入extern "C"的時候產生的匯編代碼是:

            .file "test.cxx"
            .text
            .align 2
            .globl _f
            .def _f; .scl 2; .type 32; .endef
            _f:
            pushl %ebp
            movl %esp, %ebp
            movl $1, %eax
            popl %ebp
            ret
              但是不加入了extern "C"之后

            .file "test.cxx"
            .text
            .align 2
            .globl __Z1fv
            .def __Z1fv; .scl 2; .type 32; .endef
            __Z1fv:
            pushl %ebp
            movl %esp, %ebp
            movl $1, %eax
            popl %ebp
            ret
              兩段匯編代碼同樣都是使用gcc -S命令產生的,所有的地方都是一樣的,唯獨是產生的函數名,一個是_f,一個是__Z1fv。

              明白了加入與不加入extern "C"之后對函數名稱產生的影響,我們繼續我們的討論:為什么需要使用extern "C"呢?C++之父在設計C++之時,考慮到當時已經存在了大量的C代碼,為了支持原來的C代碼和已經寫好C庫,需要在C++中盡可能的支持C,而extern "C"就是其中的一個策略。

              試想這樣的情況:一個庫文件已經用C寫好了而且運行得很良好,這個時候我們需要使用這個庫文件,但是我們需要使用C++來寫這個新的代碼。如果這個代碼使用的是C++的方式鏈接這個C庫文件的話,那么就會出現鏈接錯誤.我們來看一段代碼:首先,我們使用C的處理方式來寫一個函數,也就是說假設這個函數當時是用C寫成的:

            //f1.c
            extern "C"
            {
            void f1()
            {
            return;
            }
            }
              編譯命令是:gcc -c f1.c -o f1.o 產生了一個叫f1.o的庫文件。再寫一段代碼調用這個f1函數:

            // test.cxx
            //這個extern表示f1函數在別的地方定義,這樣可以通過
            //編譯,但是鏈接的時候還是需要
            //鏈接上原來的庫文件.
            extern void f1();

            int main()
            {
            f1();

            return 0;
            }
              通過gcc -c test.cxx -o test.o 產生一個叫test.o的文件。然后,我們使用gcc test.o f1.o來鏈接兩個文件,可是出錯了,錯誤的提示是:

            test.o(.text + 0x1f):test.cxx: undefine reference to 'f1()'
              也就是說,在編譯test.cxx的時候編譯器是使用C++的方式來處理f1()函數的,但是實際上鏈接的庫文件卻是用C的方式來處理函數的,所以就會出現鏈接過不去的錯誤:因為鏈接器找不到函數。

              因此,為了在C++代碼中調用用C寫成的庫文件,就需要用extern "C"來告訴編譯器:這是一個用C寫成的庫文件,請用C的方式來鏈接它們。

              比如,現在我們有了一個C庫文件,它的頭文件是f.h,產生的lib文件是f.lib,那么我們如果要在C++中使用這個庫文件,我們需要這樣寫:

            extern "C"
            {
            #include "f.h"
            }
              回到上面的問題,如果要改正鏈接錯誤,我們需要這樣子改寫test.cxx:

            extern "C"
            {
            extern void f1();
            }

            int main()
            {
            f1();

            return 0;
            }
              重新編譯并且鏈接就可以過去了.

              總結

              C和C++對函數的處理方式是不同的.extern "C"是使C++能夠調用C寫作的庫文件的一個手段,如果要對編譯器提示使用C的方式來處理函數的話,那么就要使用extern "C"來說明。

            posted @ 2011-05-22 17:57 simplyzhao 閱讀(263) | 評論 (0)編輯 收藏
            LC-Display
            Time Limit: 1000MSMemory Limit: 10000K
            Total Submissions: 10720Accepted: 4221

            Description

            A friend of you has just bought a new computer. Until now, the most powerful computer he ever used has been a pocket calculator. Now, looking at his new computer, he is a bit disappointed, because he liked the LC-display of his calculator so much. So you decide to write a program that displays numbers in an LC-display-like style on his computer.

            Input

            The input contains several lines, one for each number to be displayed. Each line contains two integers s, n (1 <= s <= 10, 0 <= n <= 99 999 999), where n is the number to be displayed and s is the size in which it shall be displayed. 

            The input file will be terminated by a line containing two zeros. This line should not be processed.

            Output

            Output the numbers given in the input file in an LC-display-style using s "-" signs for the horizontal segments and s "|" signs for the vertical ones. Each digit occupies exactly s+2 columns and 2s+3 rows. (Be sure to fill all the white space occupied by the digits with blanks, also for the last digit.) There has to be exactly one column of blanks between two digits. 

            Output a blank line after each number. (You will find a sample of each digit in the sample output.)

            Sample Input

            2 12345
            3 67890
            0 0

            Sample Output

                  --   --        -- 
               |    |    | |  | | 
               |    |    | |  | | 
                  --   --   --   -- 
               | |       |    |    |
               | |       |    |    |
                  --   --        -- 
            
             ---   ---   ---   ---   --- 
            |         | |   | |   | |   |
            |         | |   | |   | |   |
            |         | |   | |   | |   |
             ---         ---   --- 
            |   |     | |   |     | |   |
            |   |     | |   |     | |   |
            |   |     | |   |     | |   |
             ---         ---   ---   ---

            Source


            思路:
            這題,不會...
            無奈看其他人代碼,發現居然可以寫的這么簡潔...佩服...

            代碼:
             1 #include<stdio.h>
             2 #include<stdlib.h>
             3 #include<string.h>
             4 #define MAX_LEN 10
             5 int n;
             6 char str[MAX_LEN];
             7 const int mark[5][10][3= {
             8   /*    0       1        2        3        4        5        6        7        8        9    */
             9      0,1,00,0,00,1,00,1,00,0,00,1,00,1,00,1,00,1,00,1,0,
            10     1,0,10,0,10,0,10,0,11,0,11,0,01,0,00,0,11,0,11,0,1,
            11     0,0,00,0,00,1,00,1,00,1,00,1,00,1,00,0,00,1,00,1,0,
            12     1,0,10,0,11,0,00,0,10,0,10,0,11,0,10,0,11,0,10,0,1,
            13     0,1,00,0,00,1,00,1,00,0,00,1,00,1,00,0,00,1,00,1,0 };
            14 
            15 int
            16 main(int argc, char **argv)
            17 {
            18     int j, k, p, q, w;
            19     while(scanf("%d %s"&n, str) != EOF) {
            20         if(!n)
            21             break;
            22         for(j=0; j<5; j++) {
            23             if(j%2 == 0) {
            24                 for(p=0; str[p]!='\0'; p++) {
            25                     printf(" "); /* mark[j][k][0] */
            26                     k = str[p] - '0';
            27                     for(q=0; q<n; q++
            28                         printf("%s", mark[j][k][1]?"-":" ");
            29                     printf(" "); /* mark[j][k][2] */
            30                     printf(" ");
            31                 }
            32                 printf("\n");
            33             } else {
            34                 for(q=0; q<n; q++) {
            35                     for(p=0; str[p]!='\0'; p++) {
            36                         k = str[p] - '0';
            37                         printf("%s", mark[j][k][0]?"|":" ");
            38                         for(w=0; w<n; w++)
            39                             printf(" ");
            40                         printf("%s", mark[j][k][2]?"|":" ");
            41                         printf(" ");
            42                     }
            43                     printf("\n");
            44                 }
            45             }
            46         }
            47         printf("\n");
            48     }
            49     return 0;
            50 }
            posted @ 2010-11-09 16:46 simplyzhao 閱讀(234) | 評論 (0)編輯 收藏
            轉自:
            http://hi.baidu.com/cive/blog/item/f6899418726669b44aedbcc9.html

            ------------------------------------------------------------------------------------------------------------------

            數在計算機中是以二進制形式表示的。 
            數分為有符號數和無符號數。 
            原碼、反碼、補碼都是有符號定點數的表示方法。 
            一個有符號定點數的最高位為符號位,0是正,1是副。 

            以下都以8位整數為例, 

            原碼就是這個數本身的二進制形式。 
            例如
            0000001 就是+1
            1000001 就是-1 

            正數的反碼和補碼都是和原碼相同。 

            負數的反碼是將其原碼除符號位之外的各位求反 
            [-3]反=[10000011]反=11111100 
            負數的補碼是將其原碼除符號位之外的各位求反之后在末位再加1。 
            [-3]補=[10000011]補=11111101 
            一個數和它的補碼是可逆的。 

            為什么要設立補碼呢? 

            第一是為了能讓計算機執行減法: 
            [a-b]補=a補+(-b)補 

            第二個原因是為了統一正0和負0 
            正零:00000000 
            負零:10000000 
            這兩個數其實都是0,但他們的原碼卻有不同的表示。 
            但是他們的補碼是一樣的,都是00000000 
            特別注意,如果+1之后有進位的,要一直往前進位,包括符號位!(這和反碼是不同的!) 
            [10000000]補 
            =[10000000]反+1 
            =11111111+1 
            =(1)00000000 
            =00000000(最高位溢出了,符號位變成了0) 

            有人會問 
            10000000這個補碼表示的哪個數的補碼呢? 
            其實這是一個規定,這個數表示的是-128 
            所以n位補碼能表示的范圍是 
            -2^(n-1)到2^(n-1)-1 
            比n位原碼能表示的數多一個

            又例:
            1011 
            原碼:01011 
            反碼:01011 //正數時,反碼=原碼 
            補碼:01011 //正數時,補碼=原碼 

            -1011 
            原碼:11011 
            反碼:10100 //負數時,反碼為原碼取反 
            補碼:10101 //負數時,補碼為原碼取反+1 

            0.1101 
            原碼:0.1101 
            反碼:0.1101 //正數時,反碼=原碼 
            補碼:0.1101 //正數時,補碼=原碼 

            -0.1101 
            原碼:1.1101 
            反碼:1.0010 //負數時,反碼為原碼取反 
            補碼:1.0011 //負數時,補碼為原碼取反+1 

            總結:
            在計算機內,定點數有3種表示法:原碼、反碼和補碼

            所謂原碼就是前面所介紹的二進制定點表示法,即最高位為符號位,“0”表示正,“1”表示負,其余位表示數值的大小。

            反碼表示法規定:正數的反碼與其原碼相同;負數的反碼是對其原碼逐位取反,但符號位除外。

            補碼表示法規定:正數的補碼與其原碼相同;負數的補碼是在其反碼的末位加1。

            1、原碼、反碼和補碼的表示方法

            (1)     原碼:在數值前直接加一符號位的表示法。

            例如:       符號位   數值位

            [+7]原=    0     0000111   B

            [-7]原=    1     0000111   B

                  注意:a. 數0的原碼有兩種形式:

                                [+0]原=00000000B     [-0]原=10000000B

                            b. 8位二進制原碼的表示范圍:-127~+127

            2)反碼:

                  正數:正數的反碼與原碼相同。

                  負數:負數的反碼,符號位為“1”,數值部分按位取反。

            例如: 符號位    數值位

                  [+7]反=   0    0000111   B

                  [-7]反=   1    1111000   B

            注意:a. 數0的反碼也有兩種形式,即

                           [+0]反=00000000B

                           [- 0]反=11111111B

                       b. 8位二進制反碼的表示范圍:-127~+127

            3)補碼的表示方法

            1)模的概念:把一個計量單位稱之為模或模數。例如,時鐘是以12進制進行計數循環的,即以12為模。在時鐘上,時針加上(正撥)12的整數位或減去(反撥)12的整數位,時針的位置不變。14點鐘在舍去模12后,成為(下午)2點鐘(14=14-12=2)。從0點出發逆時針撥10格即減去10小時,也可看成從0點出發順時針撥2格(加上2小時),即2點(0-10=-10=-10+12=2)。因此,在模12的前提下,-10可映射為+2。由此可見,對于一個模數為12的循環系統來說,加2和減10的效果是一樣的;因此,在以12為模的系統中,凡是減10的運算都可以用加2來代替,這就把減法問題轉化成加法問題了(注:計算機的硬件結構中只有加法器,所以大部分的運算都必須最終轉換為加法)。10和2對模12而言互為補數。

            同理,計算機的運算部件與寄存器都有一定字長的限制(假設字長為8),因此它的運算也是一種模運算。當計數器計滿8位也就是256個數后會產生溢出,又從頭開始計數。產生溢出的量就是計數器的模,顯然,8位二進制數,它的模數為28=256。在計算中,兩個互補的數稱為“補碼”。

            2)補碼的表示: 正數:正數的補碼和原碼相同。

                 負數:負數的補碼則是符號位為“1”,數值部分按位取反后再在末位(最低位)加1。也就是“反碼+1”。

            例如:   符號位 數值位

            [+7]補=    0    0000111   B

                   [-7]補=    1    1111001   B

            補碼在微型機中是一種重要的編碼形式,請注意:

            a.采用補碼后,可以方便地將減法運算轉化成加法運算,運算過程得到簡化。正數的補碼即是它所表示的數的真值,而負數的補碼的數值部份卻不是它所表示的數的真值。采用補碼進行運算,所得結果仍為補碼。

            b.與原碼、反碼不同,數值0的補碼只有一個,即        [0]補=00000000B。

            c.若字長為8位,則補碼所表示的范圍為-128~+127;進行補碼運算時,應注意所得結果不應超過補碼所能表示數的范圍。

            posted @ 2010-11-05 17:53 simplyzhao 閱讀(241) | 評論 (0)編輯 收藏
            轉載:
            http://www.matrix67.com/blog/archives/263

            ------------------------------------------------------------------------------------------------------------------

            去年年底寫的關于位運算的日志是這個Blog里少數大受歡迎的文章之一,很多人都希望我能不斷完善那篇文章。后來我看到了不少其它的資料,學習到了更多關于位運算的知識,有了重新整理位運算技巧的想法。從今天起我就開始寫這一系列位運算講解文章,與其說是原來那篇文章的follow-up,不如說是一個remake。當然首先我還是從最基礎的東西說起。

            什么是位運算?
                程序中的所有數在計算機內存中都是以二進制的形式儲存的。位運算說穿了,就是直接對整數在內存中的二進制位進行操作。比如,and運算本來是一個邏輯運算符,但整數與整數之間也可以進行and運算。舉個例子,6的二進制是110,11的二進制是1011,那么6 and 11的結果就是2,它是二進制對應位進行邏輯運算的結果(0表示False,1表示True,空位都當0處理):
                 110
            AND 1011
            ----------
                0010  -->  2

                由于位運算直接對內存數據進行操作,不需要轉成十進制,因此處理速度非常快。當然有人會說,這個快了有什么用,計算6 and 11沒有什么實際意義啊。這一系列的文章就將告訴你,位運算到底可以干什么,有些什么經典應用,以及如何用位運算優化你的程序。


            Pascal和C中的位運算符號
                下面的a和b都是整數類型,則:
            C語言  |  Pascal語言
            -------+-------------
            a & b  |  a and b
            a | b  |  a or b
            a ^ b  |  a xor b
              ~a   |   not a
            a << b |  a shl b
            a >> b |  a shr b

                注意C中的邏輯運算和位運算符號是不同的。520|1314=1834,但520||1314=1,因為邏輯運算時520和1314都相當于True。同樣的,!a和~a也是有區別的。


            各種位運算的使用
                === 1. and運算 ===
                and運算通常用于二進制取位操作,例如一個數 and 1的結果就是取二進制的最末位。這可以用來判斷一個整數的奇偶,二進制的最末位為0表示該數為偶數,最末位為1表示該數為奇數.

                === 2. or運算 ===
                or運算通常用于二進制特定位上的無條件賦值,例如一個數or 1的結果就是把二進制最末位強行變成1。如果需要把二進制最末位變成0,對這個數or 1之后再減一就可以了,其實際意義就是把這個數強行變成最接近的偶數。

                === 3. xor運算 ===
                xor運算通常用于對二進制的特定一位進行取反操作,因為異或可以這樣定義:0和1異或0都不變,異或1則取反。
                xor運算的逆運算是它本身,也就是說兩次異或同一個數最后結果不變,即(a xor b) xor b = a。xor運算可以用于簡單的加密,比如我想對我MM說1314520,但怕別人知道,于是雙方約定拿我的生日19880516作為密鑰。1314520 xor 19880516 = 20665500,我就把20665500告訴MM。MM再次計算20665500 xor 19880516的值,得到1314520,于是她就明白了我的企圖。
                下面我們看另外一個東西。定義兩個符號#和@(我怎么找不到那個圈里有個叉的字符),這兩個符號互為逆運算,也就是說(x # y) @ y = x。現在依次執行下面三條命令,結果是什么?
            x <- x # y
            y <- x @ y
            x <- x @ y

                執行了第一句后x變成了x # y。那么第二句實質就是y <- x # y @ y,由于#和@互為逆運算,那么此時的y變成了原來的x。第三句中x實際上被賦值為(x # y) @ x,如果#運算具有交換律,那么賦值后x就變成最初的y了。這三句話的結果是,x和y的位置互換了。
                加法和減法互為逆運算,并且加法滿足交換律。把#換成+,把@換成-,我們可以寫出一個不需要臨時變量的swap過程(Pascal)。
            procedure swap(var a,b:longint);
            begin
               a:=a + b;
               b:=a - b;
               a:=a - b;
            end;

                好了,剛才不是說xor的逆運算是它本身嗎?于是我們就有了一個看起來非常詭異的swap過程:
            procedure swap(var a,b:longint);
            begin
               a:=a xor b;
               b:=a xor b;
               a:=a xor b;
            end;


                === 4. not運算 ===
                not運算的定義是把內存中的0和1全部取反。使用not運算時要格外小心,你需要注意整數類型有沒有符號。如果not的對象是無符號整數(不能表示負數),那么得到的值就是它與該類型上界的差,因為無符號類型的數是用$0000到$FFFF依次表示的。下面的兩個程序(僅語言不同)均返回65435。
            var
               a:word;
            begin
               a:=100;
               a:=not a;
               writeln(a);
            end.

            #include <stdio.h>
            int main()
            {
                unsigned short a=100;
                a = ~a;
                printf( "%d\n", a );    
                return 0;
            }

                如果not的對象是有符號的整數,情況就不一樣了,稍后我們會在“整數類型的儲存”小節中提到。

                === 5. shl運算 ===
                a shl b就表示把a轉為二進制后左移b位(在后面添b個0)。例如100的二進制為1100100,而110010000轉成十進制是400,那么100 shl 2 = 400。可以看出,a shl b的值實際上就是a乘以2的b次方,因為在二進制數后添一個0就相當于該數乘以2。
                通常認為a shl 1比a * 2更快,因為前者是更底層一些的操作。因此程序中乘以2的操作請盡量用左移一位來代替。
                定義一些常量可能會用到shl運算。你可以方便地用1 shl 16 - 1來表示65535。很多算法和數據結構要求數據規模必須是2的冪,此時可以用shl來定義Max_N等常量。

                === 6. shr運算 ===
                和shl相似,a shr b表示二進制右移b位(去掉末b位),相當于a除以2的b次方(取整)。我們也經常用shr 1來代替div 2,比如二分查找、堆的插入操作等等。想辦法用shr代替除法運算可以使程序效率大大提高。最大公約數的二進制算法用除以2操作來代替慢得出奇的mod運算,效率可以提高60%。


            位運算的簡單應用
                有時我們的程序需要一個規模不大的Hash表來記錄狀態。比如,做數獨時我們需要27個Hash表來統計每一行、每一列和每一個小九宮格里已經有哪些數了。此時,我們可以用27個小于2^9的整數進行記錄。例如,一個只填了2和5的小九宮格就用數字18表示(二進制為000010010),而某一行的狀態為511則表示這一行已經填滿。需要改變狀態時我們不需要把這個數轉成二進制修改后再轉回去,而是直接進行位操作。在搜索時,把狀態表示成整數可以更好地進行判重等操作。這道題是在搜索中使用位運算加速的經典例子。以后我們會看到更多的例子。
                下面列舉了一些常見的二進制位的變換操作。

                功能              |           示例            |    位運算
            ----------------------+---------------------------+--------------------
            去掉最后一位          | (101101->10110)           | x shr 1
            在最后加一個0         | (101101->1011010)         | x shl 1
            在最后加一個1         | (101101->1011011)         | x shl 1+1
            把最后一位變成1       | (101100->101101)          | x or 1
            把最后一位變成0       | (101101->101100)          | x or 1-1
            最后一位取反          | (101101->101100)          | x xor 1
            把右數第k位變成1      | (101001->101101,k=3)      | x or (1 shl (k-1))
            把右數第k位變成0      | (101101->101001,k=3)      | x and not (1 shl (k-1))
            右數第k位取反         | (101001->101101,k=3)      | x xor (1 shl (k-1))
            取末三位              | (1101101->101)            | x and 7
            取末k位               | (1101101->1101,k=5)       | x and (1 shl k-1)
            取右數第k位           | (1101101->1,k=4)          | x shr (k-1) and 1
            把末k位變成1          | (101001->101111,k=4)      | x or (1 shl k-1)
            末k位取反             | (101001->100110,k=4)      | x xor (1 shl k-1)
            把右邊連續的1變成0    | (100101111->100100000)    | x and (x+1)
            把右起第一個0變成1    | (100101111->100111111)    | x or (x+1)
            把右邊連續的0變成1    | (11011000->11011111)      | x or (x-1)
            取右邊連續的1         | (100101111->1111)         | (x xor (x+1)) shr 1
            去掉右起第一個1的左邊 | (100101000->1000)         | x and (x xor (x-1))


                最后這一個在樹狀數組中會用到。


            Pascal和C中的16進制表示
                Pascal中需要在16進制數前加$符號表示,C中需要在前面加0x來表示。這個以后我們會經常用到。

            整數類型的儲存
                我們前面所說的位運算都沒有涉及負數,都假設這些運算是在unsigned/word類型(只能表示正數的整型)上進行操作。但計算機如何處理有正負符號的整數類型呢?下面兩個程序都是考察16位整數的儲存方式(只是語言不同)。
            var
               a,b:integer;
            begin
               a:=$0000;
               b:=$0001;
               write(a,' ',b,' ');
               a:=$FFFE;
               b:=$FFFF;
               write(a,' ',b,' ');
               a:=$7FFF;
               b:=$8000;
               writeln(a,' ',b);
            end.

            #include <stdio.h>
            int main()
            {
                short int a, b;
                a = 0x0000;
                b = 0x0001;
                printf( "%d %d ", a, b );
                a = 0xFFFE;
                b = 0xFFFF;
                printf( "%d %d ", a, b );
                a = 0x7FFF;
                b = 0x8000;
                printf( "%d %d\n", a, b );
                return 0;
            }

                兩個程序的輸出均為0 1 -2 -1 32767 -32768。其中前兩個數是內存值最小的時候,中間兩個數則是內存值最大的時候,最后輸出的兩個數是正數與負數的分界處。由此你可以清楚地看到計算機是如何儲存一個整數的:計算機用$0000到$7FFF依次表示0到32767的數,剩下的$8000到$FFFF依次表示-32768到-1的數。32位有符號整數的儲存方式也是類似的。稍加注意你會發現,二進制的第一位是用來表示正負號的,0表示正,1表示負。這里有一個問題:0本來既不是正數,也不是負數,但它占用了$0000的位置,因此有符號的整數類型范圍中正數個數比負數少一個。對一個有符號的數進行not運算后,最高位的變化將導致正負顛倒,并且數的絕對值會差1。也就是說,not a實際上等于-a-1。這種整數儲存方式叫做“補碼”。
            posted @ 2010-11-05 17:04 simplyzhao 閱讀(308) | 評論 (0)編輯 收藏
            Anagram Groups
            Time Limit: 1000MSMemory Limit: 65536K
            Total Submissions: 2318Accepted: 649

            Description

            World-renowned Prof. A. N. Agram's current research deals with large anagram groups. He has just found a new application for his theory on the distribution of characters in English language texts. Given such a text, you are to find the largest anagram groups. 

            A text is a sequence of words. A word w is an anagram of a word v if and only if there is some permutation p of character positions that takes w to v. Then, w and v are in the same anagram group. The size of an anagram group is the number of words in that group. Find the 5 largest anagram groups.

            Input

            The input contains words composed of lowercase alphabetic characters, separated by whitespace(or new line). It is terminated by EOF. You can assume there will be no more than 30000 words.

            Output

            Output the 5 largest anagram groups. If there are less than 5 groups, output them all. Sort the groups by decreasing size. Break ties lexicographically by the lexicographical smallest element. For each group output, print its size and its member words. Sort the member words lexicographically and print equal words only once.

            Sample Input

            undisplayed
            trace
            tea
            singleton
            eta
            eat
            displayed
            crate
            cater
            carte
            caret
            beta
            beat
            bate
            ate
            abet
            

            Sample Output

            Group of size 5: caret carte cater crate trace .
            Group of size 4: abet bate beat beta .
            Group of size 4: ate eat eta tea .
            Group of size 1: displayed .
            Group of size 1: singleton .
            

            Source

            思路:
            這題將排序發揮到了極致啊呵呵,排序來排序去就AC了

            代碼:
             1 /* 47MS */
             2 #include<stdio.h>
             3 #include<stdlib.h>
             4 #include<string.h>
             5 #define MAX_NUM 30001
             6 #define MAX_LEN 36
             7 #define MAX_OUT 5
             8 struct Word {
             9     char word[MAX_LEN];
            10     char word_cmp[MAX_LEN];
            11 } words[MAX_NUM];
            12 
            13 struct Summary {
            14     struct Word *first;
            15     int count;
            16 } smmry[MAX_NUM];
            17 
            18 int total, total_category;
            19 
            20 int
            21 cmp_char(const void *arg1, const void *arg2)
            22 {
            23     return (*(char *)arg1) - (*(char *)arg2);
            24 }
            25 
            26 int
            27 cmp_words(const void *arg1, const void *arg2)
            28 {
            29     int ret = strcmp(((struct Word *)arg1)->word_cmp, ((struct Word *)arg2)->word_cmp);
            30     if(ret == 0)
            31         ret = strcmp(((struct Word *)arg1)->word, ((struct Word *)arg2)->word);
            32     return ret;
            33 }
            34 
            35 int
            36 cmp_category(const void *arg1, const void *arg2)
            37 {
            38     int ret = ((struct Summary *)arg2)->count - ((struct Summary *)arg1)->count;
            39     if(ret == 0)
            40         ret = strcmp(((struct Summary *)arg1)->first->word, ((struct Summary *)arg2)->first->word);
            41     return ret;
            42 }
            43 
            44 int
            45 main(int argc, char **argv)
            46 {
            47     int i, j, num, len;
            48     total = total_category = 0;
            49     while(scanf("%s", words[total].word) != EOF) {
            50         len = strlen(words[total].word);
            51         strcpy(words[total].word_cmp, words[total].word);
            52         qsort(words[total].word_cmp, len, sizeof(char), cmp_char); 
            53         ++total;
            54     }
            55     qsort(words, total, sizeof(struct Word), cmp_words);
            56 
            57     num = 1;
            58     for(i=1; i<total; i++) {
            59         if(strcmp(words[i].word_cmp, words[i-1].word_cmp) == 0)
            60             ++num;
            61         else {
            62             smmry[total_category].first = words+i-num;
            63             smmry[total_category].count = num;
            64             ++total_category;
            65             num = 1;
            66         }
            67     }
            68     smmry[total_category].first = words+i-num;
            69     smmry[total_category++].count = num;
            70     qsort(smmry, total_category, sizeof(struct Summary), cmp_category);
            71 
            72     total_category = total_category < MAX_OUT ? total_category : MAX_OUT;
            73     for(i=0; i<total_category; i++) {
            74         printf("Group of size %d: %s ", smmry[i].count, smmry[i].first->word);
            75         for(j=1; j<smmry[i].count; j++)
            76             if(strcmp((smmry[i].first+j)->word, (smmry[i].first+j-1)->word) != 0)
            77                 printf("%s ", (smmry[i].first+j)->word);
            78         printf(".\n");
            79     }
            80 }
            posted @ 2010-11-05 15:38 simplyzhao 閱讀(611) | 評論 (0)編輯 收藏
            僅列出標題
            共21頁: First 3 4 5 6 7 8 9 10 11 Last 

            導航

            <2025年5月>
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            統計

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            7国产欧美日韩综合天堂中文久久久久 | 久久久久亚洲精品天堂| 国产精品熟女福利久久AV| 久久电影网一区| 日本免费一区二区久久人人澡 | 精品久久久无码中文字幕天天| 久久久久亚洲AV无码麻豆| 久久精品国产乱子伦| 伊人久久精品无码二区麻豆| 亚洲欧美一级久久精品| 亚洲精品99久久久久中文字幕| 久久男人中文字幕资源站| 久久亚洲国产精品五月天婷| 亚洲精品成人网久久久久久| 久久人人爽人人爽人人片AV麻烦| 久久99热这里只有精品66| 97久久国产综合精品女不卡 | 亚洲国产日韩欧美久久| 久久久久亚洲AV成人网人人网站 | 国产精品久久久久久久久鸭| 老司机国内精品久久久久| 国产99久久久国产精品~~牛| 国产福利电影一区二区三区久久老子无码午夜伦不 | 2021最新久久久视精品爱| 亚洲精品无码成人片久久| 国产成人精品久久免费动漫| 日韩欧美亚洲综合久久影院d3| 久久久久亚洲AV成人网| 久久午夜夜伦鲁鲁片免费无码影视| 亚洲国产另类久久久精品| 人人狠狠综合久久亚洲婷婷| 一级做a爰片久久毛片免费陪| 亚洲欧洲日产国码无码久久99| 韩国无遮挡三级久久| 久久综合九色综合网站| 伊人久久免费视频| 日韩精品久久无码人妻中文字幕 | 久久噜噜电影你懂的| 精品久久久久久久久免费影院 | 热re99久久精品国产99热| av色综合久久天堂av色综合在|