青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(409) | 評論 (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 閱讀(279) | 評論 (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 閱讀(546) | 評論 (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 閱讀(483) | 評論 (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 閱讀(397) | 評論 (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 閱讀(289) | 評論 (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 閱讀(251) | 評論 (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 閱讀(273) | 評論 (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 閱讀(335) | 評論 (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 閱讀(642) | 評論 (0)編輯 收藏
僅列出標題
共21頁: First 3 4 5 6 7 8 9 10 11 Last 

導航

<2025年12月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

統計

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            99精品欧美| 91久久久精品| 亚洲你懂的在线视频| 国产精品久久久久久久久动漫| 久久久久在线观看| 欧美三级电影网| 最新国产成人av网站网址麻豆| 欧美激情精品久久久久久大尺度 | 久久久久国内| 国产精品视频网址| 夜夜嗨一区二区三区| 亚洲免费观看| 欧美激情二区三区| 亚洲欧美成人| 亚洲欧洲中文日韩久久av乱码| 欧美日韩国产综合网| 亚洲国产精品视频一区| 亚洲欧洲一区二区在线观看| 亚洲蜜桃精久久久久久久| 91久久综合亚洲鲁鲁五月天| 国产精品专区一| 亚洲精品久久久久久一区二区 | 一本到高清视频免费精品| 久久亚洲电影| 欧美第一黄色网| 亚洲激情欧美激情| 欧美激情综合在线| 亚洲精品免费网站| 国产情人综合久久777777| 欧美大片免费观看在线观看网站推荐| 欧美精品一区三区在线观看| 蜜臀av性久久久久蜜臀aⅴ四虎 | 国产色产综合产在线视频| 亚洲资源av| 日韩亚洲欧美成人| 欧美一区二区三区电影在线观看| 欧美一进一出视频| 欧美久久一区| 久久综合久久综合九色| 欧美色欧美亚洲另类七区| 亚洲精品在线观| 午夜影院日韩| 欧美日韩三级一区二区| 亚洲无线视频| 麻豆精品网站| 激情成人亚洲| 欧美国产亚洲视频| 欧美国产激情| 亚洲在线1234| 国产最新精品精品你懂的| 免费成人激情视频| 美女精品在线| 亚洲深夜av| 韩国成人福利片在线播放| 欧美激情国产日韩| 小嫩嫩精品导航| 亚洲国产日韩欧美在线动漫| 亚洲一区二区三区精品在线观看| 国产亚洲精品激情久久| 欧美成人在线网站| 性感少妇一区| 亚洲精品网站在线播放gif| 亚洲六月丁香色婷婷综合久久| 欧美日韩中文字幕| 久久精品99| 一区二区欧美日韩| 欧美成人在线免费观看| 一色屋精品亚洲香蕉网站| 午夜欧美大片免费观看| 欧美呦呦网站| 亚洲精品国偷自产在线99热| 一本在线高清不卡dvd| 国产日韩欧美自拍| 欧美私人网站| 免费中文字幕日韩欧美| 先锋资源久久| 蜜桃久久精品乱码一区二区| 亚洲综合色网站| 国产亚洲一区在线| 欧美午夜美女看片| 欧美激情一区二区三区| 午夜在线一区二区| 亚洲网址在线| 亚洲美女av网站| 午夜视频在线观看一区| 99国产一区二区三精品乱码| 欧美三级视频在线| 午夜一区在线| 嫩草成人www欧美| 亚洲精品在线观看免费| 黑人巨大精品欧美一区二区小视频| 国产精品第十页| 久久av一区二区三区| 老司机亚洲精品| 99re6热只有精品免费观看| 欧美日本韩国| 亚洲伦理网站| 久久久久一区二区三区| 亚洲麻豆视频| 国产亚洲综合性久久久影院| 免费中文日韩| 亚洲一区二区免费视频| 猛男gaygay欧美视频| 久久婷婷蜜乳一本欲蜜臀| 亚洲免费播放| 99热在这里有精品免费| 99re热这里只有精品免费视频| 国产精品一二三四| 欧美高清视频在线| 欧美高清在线| 欧美日韩国产丝袜另类| 久久九九精品99国产精品| 久久激情婷婷| 久久久久国色av免费看影院 | 亚洲欧美日韩国产综合| 亚洲欧美中文日韩在线| 性色av一区二区三区红粉影视| 亚洲永久视频| 欧美一区二视频在线免费观看| 亚洲一区二区三区四区视频| 狠狠色综合色综合网络| 136国产福利精品导航| 亚洲国内自拍| 一区二区三区在线视频播放| 欧美偷拍一区二区| 国产精品乱子乱xxxx| 欧美国产视频一区二区| 欧美日韩xxxxx| 国产欧美精品国产国产专区| 欧美日韩高清在线| 国产精品一区二区久激情瑜伽| 欧美国产亚洲另类动漫| 欧美在线影院| 亚洲一区日韩在线| 一本色道久久综合狠狠躁篇怎么玩| 一区二区三区视频在线播放| 亚洲国产精品精华液2区45| 亚洲伦理中文字幕| 午夜精品短视频| 亚洲综合日韩在线| 久久人人爽国产| 久久五月天婷婷| 欧美在线一区二区三区| 亚洲欧美在线aaa| 亚洲一区二区在线看| 亚洲午夜视频| 中文精品视频一区二区在线观看| 欧美在线精品免播放器视频| 欧美99在线视频观看| 中文av字幕一区| 久久天天综合| 麻豆成人小视频| 欧美成年人网| 久久午夜精品一区二区| 亚洲深夜福利| 欧美xart系列在线观看| 国产日韩欧美视频| 一区二区日韩伦理片| 久久在线免费观看| 欧美高清在线一区| 午夜精品美女久久久久av福利| 欧美bbbxxxxx| 一区二区三区无毛| 久久se精品一区精品二区| 亚洲精品久久久蜜桃| 美女视频黄a大片欧美| 国产精品一区二区三区观看 | 91久久久久久久久久久久久| 欧美亚洲一区三区| 久久婷婷丁香| 欧美激情四色 | 亚洲第一伊人| 久久精品一级爱片| 欧美福利影院| 悠悠资源网久久精品| 亚洲精品视频在线观看免费| 久久视频在线看| 欧美一区综合| 国产日韩视频一区二区三区| 中文在线不卡| 久久久精彩视频| 亚洲欧美电影在线观看| 国产精品久久久久aaaa樱花| 国产主播精品在线| 亚洲另类自拍| 国产精品自在线| 精品动漫3d一区二区三区| 久久激情五月激情| 欧美一级免费视频| 国产日韩免费| 一本色道久久综合精品竹菊| 亚洲高清一区二| 午夜精品福利一区二区蜜股av| 欧美在线黄色| 国产日韩av一区二区| 亚洲人成人一区二区三区| 午夜欧美不卡精品aaaaa| 欧美大片免费观看| 久久影院午夜片一区| 亚洲日本中文|