December 2007 Archives

看今日中国人过圣诞节

| 1 Comment
    快到圣诞节了,不论哪个商店、超市还是商场,随处可见圣诞老人的装扮和圣诞树。而在中国过洋节是一种时尚,而在相隔只有5天的元旦就没有圣诞节那样的装饰,很少见商场有高高悬挂的红灯笼,很少见到中国传统节日的装饰氛围,圣诞节如此,情人节也如此,似乎中国人已经丢掉了某些东西。

    今年元旦的假期你将怎么过呢?

PostgreSQL 中文编码使用问题

| No Comments
在创建PostgreSQL  Database时,字符编码值BIG5, GBK, GB18030已经为无效值。
如:
[postgres@localhost postgres]$/usr/local/postgresql-8.2.4/bin/initdb -D /u/postgres/gbkdata/ -E GBK -U root
initdb: "GBK" is not a valid server encoding name
目前建议采用UTF8或者EUC_CN、EUC_TW、MULE_INTERNAL
这里仅仅与其他数据库做一个对比而已。

看中国雅虎的产品

| No Comments
最近中国雅虎推出了一个积分项目——雅虎全能搜用户俱乐部(http://fun.yahoo.cn/),与阿里妈妈联手,合作推广。就项目而言,没有什么可说的,一切做得有条有理,但是对产品定向而言,我感觉是走了一个很长的弯路。

在用c写程序时,很多时候需要存储一些简单的数据,如果为此而用mysql数据库就有些大才小用了,可以把这些数据以结构的形写入文件,然后再需要时读取文件,取出数据。

原码、补码和反码

| No Comments
原文:http://blog.chinaunix.net/u/20/showart_438418.html

在计算机里如何表示整数?


整数有无穷多个,在计算机里,通常我们只能表示出 其中的一部分。假如我们用 n 个比特来表示一个整数。1 个比特有 2 个状态,n 个比特就有 2^n 个状态,把这 2^n 个状态的集合记为 A. 显然,用 A,我们可以与 n 个整数建立起一一对应。我们还希望 A 所表示的整数能够象整数那样地运算---整数,象整数那样运算,这是不是一句废话?数学中的整数相加,仍然是一个整数,但 A 里两个整数相加,我们却无法保证它们的和仍在 A 中,用代数的术语来讲,叫做 “不满足封闭性”,这是个很坏的性质。



一、补码




不 过数学上有处理这个问题的成熟方案,如果我们能后退一步,让 A 表示的是模 |A| 的剩余类,则加法运算马上就封闭了。而且这个时候 A 不仅可以与 2^n 个整数对应起来,而且,在某种意义下,可以与整数环 Z 对应起来。用代数的观点,这个 “某种意义”就是所谓的同态。

整数有两种封闭运算,一种是加法,另一种是乘法。A 作为模 2^n 的剩余类,也有加乘两种运算。定义 Z 到 A 的映射
f(x) = m mod 2^n

f 是一个同态,也就是说,f 满足这样的良好性质:

f(x+y) = f(x) + f(y)
f(xy) = f(x)f(y)

我 们通常使用 10 进制数,在这个进制下,f(x) 并不容易计算,但是在计算机里,本质的表示是二进制,于是 f(x) 的运算变得出奇地简单。如果 x 小于 2^n,则 x 的 2 进制表示就是 f(x),如果 x>=2^n,则要求其模 2^n 的余数,这恰好是 x 二进制表示的最低 n 位,换句话说,简单地把高位抛弃就行了。顺便指出,f(0)=0, f(1)=1.

我们来看一看 A 中的加法,f(x)+f(y), 若结果小于 2^n,则运算自然封闭,如果 f(x)+f(y) >= 2^n,则取其最低的 n 位,用电路实现时,可以简单地扔掉高位,保留低位。

到目前为止,一切都很好,但是减法怎么办呢?对整数运算而言,减去 a 不过是加上 a 的相反数的同义语。只要对 A 中的每个元素,能容易计算出其相反数就可以了。理论上 f(x) 的相反数就是

f(-f(x))

不过这个好像不容易计算,因为我们现在并没有给出 A 中“负数”的概念,事实上 A 是模 2^n 的剩余类环,根本就没有所谓的负数。

这个困难也是容易处理的。作为 f(x) 的相反数,-f(x) 应该满足这样的性质:

-f(x) + f(x) = f(0) = 0

所 以我们只要有在 A 中找一个元素,使得它与 f(x) 的和是 0 就可以了。但是 f(x) 本身可能含有很多比特 1,加上一个数能使它们变成 0 吗? 考虑到 A 中的加法要模去一个 2^n,这个问题实际上很好办,只要让求出的和是 2^n 就可以了。所以难发现 -f(x) 就是把 f(x) 的比特“取反”---即 0 变 1, 1 变 0,并加上 1 就得到了 -f(x)。容易验证:

f(-x) = - f(x).


现在我们回过头来看前面的一句话,红色部分:

“我们通常使用 10 进制数,在这个进制下,f(x) 并不容易计算,但是在计算机里,本质的表示是二进制,于是 f(x) 的运算变得出奇地简单。如果 x 小于 2^n,则 x 的 2 进制表示就是 f(x),如果 x>=2^n,则要求其模 2^n 的余数,这恰好是 x 二进制表示的最低 n 位,换句话说,简单地把高位抛弃就行了。顺便指出,f(0)=0, f(1)=1.”

红色那句话简直是胡扯,因为没有考虑到负数的情况。但 f(x) 容易计算这句话并没有错,因为当 x 为负数时,我们可以利用 f(x) = -f(-x)。 由于 -x 是正的,f(-x) 容易计算,之后 -f(x) 也不过是取反加 1 而已。

好,到目前为止---在数学世界里,简直是完美的。但是回到现实, A 里头真的没有负数,怎么办?整数能比较大小,A 里头的数又怎么办?

这时候,我们可以用一个不太完美的方案,把 A 里头的元素再映射回整数 Z 中,如果只需要无符号的数,则变换为

g(u) = u,    0<= u <2^n

其实就是不把 A 中的元素模 2^n 的剩余类,而直接看成整数。不过这时的运算就要考虑溢出了。如果是无符号的情形,运算的结果仍是模 2^n 的余数,外加一个溢出标志。

如果要考虑负数,如果没有特别的理由,则要求正负个数大致相等是自然的。可以考虑让 0 代表 0, 1~2^{n-1}-1 代表正数,2^{n-1}+1~2^n-1 代表负数。丢掉一个 2^{n-1} 是因为希望正数和负数刚好配对,若 u 代表负数,则其落在 2^{n-1}+1~2^n-1 中,但它代表负几呢?当然是负 -u 了。从两个相反数之和为 0 ,或 2^n 的观点,-u 就是 2^n-u, 而 u 则是 -(-u) 即 u-2^n。

2^{n-1} 是个麻烦,在 A 中,它的相反数就是自己,把它当正数,负数都不大合理。出于完整性考虑,随便选一个好了。在这里我们让 2^{n-1} 为负数,理由是它的最高位是 1,跟其它“负数”长得比较象。

换个角度看,模 n 的剩余类,或者余数为 0,1,...,2^{n-1}, 2^{n-1}+1, ..., 2^n-1. 这些余数也可以表示为:

0,1~2^{n-1}, 2^n-(2^{n-1}-1), ..., 2^{n}-1

我们刚才所做的就是把上面数列中 2^{n} -r (1<= r<= 2^{n-1}-1)类型的的数对应为负数 -r 而已。用代数的术语,就是在陪集中选取了不同的代表元。

于是我们定义  A  到  Z  的变换,使得

当 0<= u <= 2^{n-1} 时, g(u) = u
当 2^{n-1} <u < 2^n 时,g(u)=u - 2^n

当然,这时运算起来有可能溢出,但结果仍可以看成模 2^n 的余数,外加一个溢出标记。


上面所说的就是补码。



二、反码


抽象地看,反码与补码只有一个区别,同样的 n 比特状态集合 A,反码让这些元素表示模 2^n-1 的剩余类,而补码模 2^n。于是从 Z 到 A 的映射定义为

f(x) = x mod 2^n-1

不过且慢,A 的大小是 2^n,而模 2^n-1 的余数只有 2^n-1 个? 是的,这是反码一个不完美的地方,它浪费了全 1 的码字,不过我们可以把全 1 的和全 0 的数看成一样的。

f 同样是个环同态,满足

f(x+y) = f(x) + f(y)
f(xy) = f(x)f(y)
俄且 f(0)=0, 或者全 1, f(1) = 1.

f(x) 可以计算如下,设
x = 2^n q + r,

则由于 2^n = 1 mod (2^n-1),所以

x = q + r  (mod 2^n -1)

若然 q+r 仍大于等于 2^n,则递归使用上述步骤。当然也可以直接去模 2^n-1,但上面的处理充分利用了二进制表示。而且当 x 为负数时,我们有两外的处理方法,见后面相反数的部分。

f(x) 能求出后,A 中的加法运算和乘法运算也就容易处理了,若 f(x)+f(y)<2^n,则不作特别处理,如果 f(x)+f(y) >=2^n,则结果为 f(f(x)+f(y)) 即把第 n+1 比特加到最低比特上。对于乘法,f(x)f(y) 可以多出n-1 位,处理方法是把第 n+i 比特加到第 i 比特上,或者说把高出 n 位的比特都右移 n 位并加在低位上, 如果仍然越界,则重复上述步骤。从这里可以看到反码的一个弱点,它的越界处理比较麻烦,而补码直接把越界的位丢掉就是了。

A 中的相反数如何求? -f(x) + f(x) = f(0) = 0, 加出一个全零比较难办,但加出一个全 1 不是问题,所以我们可以让 -f(x) 为 x 的取反,即 0 变成 1, 1 变成 0。于是求相反数的问题解决了。

同样,我们可以考虑在反码中引入正数,负数,这个与补码的类似,这里就不多说了。

有 趣的是 2^n 几乎不可能是素数,而 2^n-1 有可能. 2^n-1 形的素数称为梅森素数。如果 2^n-1 是素的,则 A 中非零元素都可求逆。那么对应于 32 位和 64 位计算机的,将会是 31 位计算机和 61 位计算机,看上去很不错嘛,期待中。


这样就结束了我们对反码的讨论。




三、原码


这个没有什么可说的,2^n 个状态直接表示 0~2^n-1,如果要引入负数,则让最高位为 1 的表示负数, 所以 0x 代表 x,而 1x 代表 -x.

原码最好的地方是它简单,最不好的地方在于它没有良好的代数结构。

关于md5和sha1

| No Comments
日积月累,积累了一个大约50G左右的词典可供md5以及sha1的逆向查询,基本上常见的所有的md5编码和sha1都可以逆向查询获得正确的字串。
详情见:http://renark.huhoo.net/crypt.cgi
目前没有较好的数据库空间,索引有限,如果有愿意提供比较大的数据库空间的朋友可以贡献一点哟~。

1.jpg今年的12月1日是北京市第十四个艾滋病宣传日,我和公司同事一起参加一次在居庸关的健走活动,权当锻练身体了吧。

最近的心情也很郁闷,顺便到处走走释放一下郁结, :)

顺便Show下照片。






Archives

Recent Comments

  • rao.chenlin: const-c.inc和const-xs.inc这两个的写法能不能详细说说啊。perlxs的中文资料不好找~~多谢多谢 read more
  • rao.chenlin: 我是openSUSE12.1的i686,QQ群获取的群友昵称(包括自己)是乱码~其他一切OK read more
  • cnangel: 已经证明在fedora、ubuntu的i686以及x86_64平台都可以使用。 read more
  • fdcwqmst: 总算找到一点靠谱的博文了 read more
  • Cnangel: 所以说嘛,无奈~ read more
  • 贝贝: 提示你了他们怎么赚钱阿?就是要让你在不知不觉中就花了好多钱 read more
  • Cnangel: please say chinese read more
  • david: hello , i need you help , but i dont read more
  • Cnangel: 问题出错在: /root/phpdev/php-5.3.3/ext/php5cpp/php5cpp.cpp:65: error: invalid conversion from ‘const zend_function_entry*’ to ‘_zend_function_entry*’ read more
  • craboy1: 我make出现了下边的错误: g++ -I. -I/root/phpdev/php-5.3.3/ext/php5cpp -DPHP_ATOM_INC -I/root/phpdev/php-5.3.3/ext/php5cpp/include -I/root/phpdev/php-5.3.3/ext/php5cpp/main -I/root/phpdev/php-5.3.3/ext/php5cpp -I/usr/include/php5 -I/usr/include/php5/main read more

Pages

Powered by Movable Type 5.2.2

December 2012

Sun Mon Tue Wed Thu Fri Sat
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31          
Creative Commons License
This blog is licensed under a Creative Commons License.

About this Archive

This page is an archive of entries from December 2007 listed from newest to oldest.

November 2007 is the previous archive.

January 2008 is the next archive.

Find recent content on the main index or look in the archives to find all content.