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 阅读(367) | 评论 (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 阅读(234) | 评论 (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 阅读(497) | 评论 (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 阅读(439) | 评论 (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 阅读(361) | 评论 (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 阅读(240) | 评论 (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 阅读(204) | 评论 (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 阅读(219) | 评论 (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 阅读(284) | 评论 (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 阅读(579) | 评论 (0)编辑 收藏
仅列出标题
共21页: First 3 4 5 6 7 8 9 10 11 Last 

导航

<2024年5月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜