作者被禁止或删除 内容自动屏蔽

346196247

mci2004 发表于 2013-02-03 16:59
2^n - 1在计算机里面用二进制表示为

1000000....0

可以勉强可以懂，
我只看到你的然后那里就不懂了

mci2004

0111111111...111  =

     0100000000...000
+  0010000000...000
     0001000000...000
                         ...
     00000000000001


现在呢？

字符宽度不一样，要怎么对其呢？谁来指导下

346196247

mci2004 发表于 2013-02-03 17:35
0111111111...111  =

     0100000000...000

懂了，这个是看懂的懂,了  

Ager

楼主是不是故意来搞笑的呀？

如果楼主是真不懂的话，那么，恐怕讲数列、数学归纳法什么的，理解曲线岂不是更陡？

不如画个图表，更加直观：

1. 
   
2. 0: oo
   
3. 1: oo
   
4. 2: oooo
   
5. 3: oooooooo
   
6. 4: oooooooooooooooo
   

复制代码

上图中：
第0行的dot数量是2；
第1行的dot数量是2；
第2行的dot数量是4；
第3行的dot数量是8；
第4行的dot数量是16；
—— 第N行的dot数量是2^N。（N=1,2,3,……，即：N虽是从0开始计的，但前述等量关系只适用于N=1,2,3……）

又，将第0行+第1行，即可以得到第2行（即让第1行自己加自己，俗称翻番）；
将第0行+第1行+第2行，即可以得到第3行（即让第2行自己加自己，俗称翻番）；
将第0行+第1行+第2行+第3行，即可以得到第4行（即让第3行自己加自己，俗称翻番）；
……
即从第0行累加到N行（N=1,2,3,……），dot数量之和总是第N+1行的dot数量。
（第N行自己加自己，翻番，就可以生成第N+1行。）

形而上的说法就是：
2 + 2^1 + 2^2 + 2^3 + ... + 2^N == 2^(N+1)
（N=1,2,3,……，即：N虽依然是从0开始计的，但这里的等式只适用于N=1,2,3……）

将等号左边首项2拆分为1+1，得到：
1 + 1 + 2^1 + 2^2 + 2^3 + ... + 2^N == 2^(N+1)

上式等号两边同时减去1，得到一个依然成立的等式：
1 + 2^1 + 2^2 + 2^3 + ... + 2^N == 2^(N+1) -1

即：
2^0 + 2^1 + 2^2 + 2^3 + ... + 2^N == 2^(N+1) -1

令上式中的 N = n-1，得到：
2^0 + 2^1 + 2^2 + 2^3 + 2^(n-1) == 2^n -1

（n=1,2,3,……）

呵呵，以上不是基于公理系统的数学证明，只是帮助楼主体会数学现象的直观，仅供参考，呵呵 —— ：）

mci2004

回复 15# Ager


    Ager大虾  爆照啦！？

captivated

呵呵. folklore 说得没错，这是等比数列求前N项和的问题.

设1 + 2 + 2 ^ 2 + 2 ^ 3 + 2 ^ 4 + 2 ^ 5 + 2 ^ 6 +... +  2 ^ (n - 1) = S ---- (1)
于是
(1 + 2 + 2 ^ 2 + ... + 2 ^ (n - 1)) * 2 = S * 2 ---- (2)
于是
(2) - (1) = 2 ^ n - 1 = S
===========================================

还可以用二项式定理得出相同的结论, 将下式用二项式定理展开, 即可得出证明:
(1 + 1) ^ n
===========================================

为什么我说这是计算机的基础题目呢？ 因为这和2's complement密切相关.
我们知道, 目前的大多数计算机内部表示整数都是使用补码的方式. 让我们回顾一下, 最高位为符号位:
原码:
正整数的原码, 符号位为0, 其余位为其二进制表示.
负整数的原码, 符号位为1, 其余位为其正整数二进制表示.

1's complement, 也就是反码, 其表示方式是:
正整数的反码, 符号位为0, 其余位为其二进制表示.
负整数的反码, 符号位为1, 其余位为其正整数二进制表示按位取反.

2's complement, 也就是补码, 其表示方式是:
正整数的补码, 符号位为0, 其余位为其二进制表示.
负整数的补码, 符号位为1, 其余位为其正整数二进制表示按位取反再 + 1.

比如, 假设我们只有一个字节来表示一个整数, 那么, 我们只有7位来表示"真正的数值", 最高位为符号位.
比如 -3 的补码表示, 应该是:
+3补码表示:
0000 0011
那么-3的补码表示(最高位1, 其余位按位取反 + 1):
1111 1101

正整数二进制表示按位取反(现在, 让我们不再care符号位什么的)意味着什么? 意味着:
  1111 1111    ---- 2 ^ 8 - 1 == 2 ^ 7 + 2 ^ 6 + ... + 2 ^ 1 + 2 ^ 0
- 0000 0011    ---- +3
-------------------
  1111 1100
意味着, 2 ^ n - 1 - 3. -- 意味着, 我们对一个正整数按位取反, 其实就是 :       2 ^ n - 1 - 这个正整数.
那么, 2 ^ n - 1 - 3 + 1 意味着什么? 意味着 2 ^ n - 3, 也就是说, 我们对一个正整数取反再加一, 其实就是:     2 ^ n - 这个正整数.
我们假设了我们只有一个字节, 因此上面两个"意味"中, n 取 8.
啊哈! 让我们看看! 我们假设一个表盘, 这个表盘一共有256个刻度, 从刻度0开始到刻度255. 那么我顺时针走一步, 意味着数值 + 1. 让我们看看, 255 + 1 == 256, 唔, 似乎我们又回到了表盘的起点? 表盘的起点是什么? 啊, 是0！
于是我们有:  2 ^ 8 - 3 == 0 - 3.
唔, 所以补码表示是怎么得来的, 明白了吗? 我们称256为一个字节的模. 一个负整数的补码, 说白了就是模减去其正整数, 明白了吗? 然后计算机算加减法就可以不再care符号位了.

===========================================

呵呵. LZ挺认真的. LZ看了我的解答估计很想K我罢(弄得高深莫测结果这么简单神马的, 哈哈)? 谁叫你不思考呢... 这高中数学嘛.

老实说, 我觉得LZ 93后, 虽然语文还不太好, 表达叙述没有层次和清晰感什么的, 但还是挺可爱的. 当时出这个题目想要稍微调戏一下LZ, LZ上当了, 哈哈, 开心~ LZ以后可以用这个调戏下00后什么的, 嗯, 主要是一连串的2很双关的说, 哈哈. 这里发现LZ既然如此认真可爱, 那么叔叔我就收回调戏LZ时的话, LZ你不2哈, 是叔叔我2了~

===========================================

Ager

mci2004 发表于 2013-02-03 18:12
回复 15# Ager

爆照啦！？

是的。此头像是我的真人照片，呵呵：）

captivated

17楼为本人解答. Ager大侠的解答与我殊途同归哈。

346196247

captivated 发表于 2013-02-03 18:37
呵呵. folklore 说得没错，这是等比数列求前N项和的问题.

设1 + 2 + 2 ^ 2 + 2 ^ 3 + 2 ^ 4 + 2 ^ 5 + 2 ...

大神，我那帖子本来就是求批评的，哈哈，我没有上当，我把你们出的这个问题去借用去问另外一个，非常牛的样子的人，他才是真的上当了呢{:3_189:} 我把你的题目改了一改