g*********s
发帖数: 1782 | 1 unsigned bit_add(unsigned int x, unsigned int y) {
unsigned int carry = x & y;
unsigned int result = x ^ y;
while ( carry != 0 ) {
unsigned int shifted_carry = carry << 1;
carry = result & shifted_carry;
result ^= shifted_carry;
}
return result;
}
没想明白正确性。另外如果扩展到int怎么改？ |
X****r
发帖数: 3557 | 2 没学过加法器吗？
http://en.wikipedia.org/wiki/Adder_(electronics)
【在 g*********s 的大作中提到】
: unsigned bit_add(unsigned int x, unsigned int y) {
: unsigned int carry = x & y;
: unsigned int result = x ^ y;
: while ( carry != 0 ) {
: unsigned int shifted_carry = carry << 1;
: carry = result & shifted_carry;
: result ^= shifted_carry;
: }
: return result;
: }
|
g*********s
发帖数: 1782 | |
g*********s
发帖数: 1782 | 4 试着手工验证了一下，这个算法算result[0],[1],[2]没问题。但是result[3]的形式就很复杂
了，看不清。
谁能给个证明？
【在 g*********s 的大作中提到】
: 这段代码模拟的是哪种呢？
|
P********l
发帖数: 452 | 5 这样是不是容易理解点？
add(x,y){
if(y==0)
return x;
c = (x & y) << 1; //carry
r = x ^ y; //current bit.
return add(r, c);
} |
g*********s
发帖数: 1782 | 6 还是不理解这个递归表达式。
假设x和y都是四位，最坏情况递归四次结束。那第三次递归结束，第四次递归开始之前，r的最高位代表
什么？c2呢？
主要的困惑在于，这里的位操作是针对整个二进制串的。那前面算低位的时候，高位还没算到的部分也
可能变化很多次。这样算到高位时已经和原来的值相去甚远，怎么保证正确性呢？希望能看到严格证
明。
【在 P********l 的大作中提到】
: 这样是不是容易理解点？
: add(x,y){
: if(y==0)
: return x;
: c = (x & y) << 1; //carry
: r = x ^ y; //current bit.
: return add(r, c);
: }
|
p***o
发帖数: 1252 | 7 http://www.ece.tamu.edu/~sshakkot/courses/ecen248/csa-notes.pdf
前，r的最高位代表
还没算到的部分也
望能看到严格证
【在 g*********s 的大作中提到】
: 还是不理解这个递归表达式。
: 假设x和y都是四位，最坏情况递归四次结束。那第三次递归结束，第四次递归开始之前，r的最高位代表
: 什么？c2呢？
: 主要的困惑在于，这里的位操作是针对整个二进制串的。那前面算低位的时候，高位还没算到的部分也
: 可能变化很多次。这样算到高位时已经和原来的值相去甚远，怎么保证正确性呢？希望能看到严格证
: 明。
|
g*********s
发帖数: 1782 | 8 an interesting article to read. but i don't see the connection to my
question.
this article seems also to do sequence bit-add, while the code i posted
is always doing op on all bits in parallel.
it is easy to see once one bit gets its final value, the value will not
change. but the question is how to prove:
r(i) = x(i)^y(i)^c(i-1) = x(i)^y(i)^...^...^..., where ... means the bit
being "xor"-ed in the loop/recursion.
i tried to use analytical form to prove it. but for i = 0, 1, 2, it's
easy. when i is big, the analytical form is complicated and hard to
reduce. so i don't think this is a right direction.
【在 p***o 的大作中提到】
: http://www.ece.tamu.edu/~sshakkot/courses/ecen248/csa-notes.pdf
:
: 前，r的最高位代表
: 还没算到的部分也
: 望能看到严格证
|
p***o
发帖数: 1252 | 9
That's the reason you have no clue how that code works.
The code you posted applies CSA again and again but always
set the carry input to 0. Someone ahead even turns these
iterations into a tail recursion.
Take any introductory VLSI or architecture textbook. The proof
should be easy. That's why no one bother to prove it to you.
【在 g*********s 的大作中提到】
: an interesting article to read. but i don't see the connection to my
: question.
: this article seems also to do sequence bit-add, while the code i posted
: is always doing op on all bits in parallel.
: it is easy to see once one bit gets its final value, the value will not
: change. but the question is how to prove:
: r(i) = x(i)^y(i)^c(i-1) = x(i)^y(i)^...^...^..., where ... means the bit
: being "xor"-ed in the loop/recursion.
: i tried to use analytical form to prove it. but for i = 0, 1, 2, it's
: easy. when i is big, the analytical form is complicated and hard to
|
g*********s
发帖数: 1782 | 10
from wiki:
A carry-save adder is a type of digital adder, used in computer
microarchitecture to compute the sum of three or more n-bit numbers in
binary.
so where's the 3rd number coming from? just assuming an constant 0?
【在 p***o 的大作中提到】
:
: That's the reason you have no clue how that code works.
: The code you posted applies CSA again and again but always
: set the carry input to 0. Someone ahead even turns these
: iterations into a tail recursion.
: Take any introductory VLSI or architecture textbook. The proof
: should be easy. That's why no one bother to prove it to you.
|
|
|
p***o
发帖数: 1252 | 11
It's usually used for multiplication where you need to add n n-bit
numbers (shifted) together.
【在 g*********s 的大作中提到】
:
: from wiki:
: A carry-save adder is a type of digital adder, used in computer
: microarchitecture to compute the sum of three or more n-bit numbers in
: binary.
: so where's the 3rd number coming from? just assuming an constant 0?
|
g*********s
发帖数: 1782 | 12 sorry, from CLRS, carry-save addition is a Theta(1) operation such that
x + y + z = u + v. it still needs a carry-lookahead to get the final
result in O(logN).
so how come this code represents carry-save addition? it means carry-
lookahead instead?
【在 p***o 的大作中提到】
:
: It's usually used for multiplication where you need to add n n-bit
: numbers (shifted) together.
|
g*********s
发帖数: 1782 | 13 one more observation:
carry-lookahead takes O(logN), while this code may take O(N) loop
iteration in worst case. try 0111 + 0001 and u'll see:
carry, result:
0001, 0110
0010, 0100
0100, 0000
0000, 1000
so how come this code is a "carry-save" or "carry-lookahead" adder? my
best guess is this is just a variant of ripple-adder.
transition from iterative version to tail recursion is an independent
topic. i don't see how it helps to understand the code...
that
【在 g*********s 的大作中提到】
: sorry, from CLRS, carry-save addition is a Theta(1) operation such that
: x + y + z = u + v. it still needs a carry-lookahead to get the final
: result in O(logN).
: so how come this code represents carry-save addition? it means carry-
: lookahead instead?
|
t****t
发帖数: 6806 | 14 this IS ripple adder, no one said it's carry look ahead.
【在 g*********s 的大作中提到】
: one more observation:
: carry-lookahead takes O(logN), while this code may take O(N) loop
: iteration in worst case. try 0111 + 0001 and u'll see:
: carry, result:
: 0001, 0110
: 0010, 0100
: 0100, 0000
: 0000, 1000
: so how come this code is a "carry-save" or "carry-lookahead" adder? my
: best guess is this is just a variant of ripple-adder.
|
g*********s
发帖数: 1782 | 15 the link of carray-save adder was posted. of course, u can still say "no
one said...", and i agree.
so for this ripple adder, how does it works?
【在 t****t 的大作中提到】
: this IS ripple adder, no one said it's carry look ahead.
|
p***o
发帖数: 1252 | 16 You got lost ... Here is what your code looks like:
input a, b;
while (b != 0)
{
(s,c)=CSA(a,b,0);
a=s, b=2*c;
}
output a;
CSA ensures s+2c == a+b so the loop keeps a+b unchanged.
The loop terminates since it eliminates bits in b from right.
【在 g*********s 的大作中提到】
: one more observation:
: carry-lookahead takes O(logN), while this code may take O(N) loop
: iteration in worst case. try 0111 + 0001 and u'll see:
: carry, result:
: 0001, 0110
: 0010, 0100
: 0100, 0000
: 0000, 1000
: so how come this code is a "carry-save" or "carry-lookahead" adder? my
: best guess is this is just a variant of ripple-adder.
|
t****t
发帖数: 6806 | 17 ok, let me make it clear.
usually when we say carry-save, you get
c+s+n -> c'+s'
where c is carry, s is sum, n is new number. this reduces 3 number into 2.
if you consider pair (c,s) as one entity, this efficiently implements
accumulator.
when we say ripple-adder, you get
a+b -> s
this program implements ripple-adder by applying carry-save repeatedly, when
setting n=0 everytime. so what you saw is
c+s -> c'+s' (while c!=0)
it's easy to see this loop is bounded when we have limited number of bits:
since c' always has more 0 at LSB than c, c will eventually get to 0.
【在 g*********s 的大作中提到】
: sorry, from CLRS, carry-save addition is a Theta(1) operation such that
: x + y + z = u + v. it still needs a carry-lookahead to get the final
: result in O(logN).
: so how come this code represents carry-save addition? it means carry-
: lookahead instead?
|
t****t
发帖数: 6806 | 18 for adders, carry-save, carry-look ahead, ripple, are all different.
【在 g*********s 的大作中提到】
: the link of carray-save adder was posted. of course, u can still say "no
: one said...", and i agree.
: so for this ripple adder, how does it works?
|
g*********s
发帖数: 1782 | 19 16th and 17th floor very clear. thx for both.
【在 t****t 的大作中提到】
: for adders, carry-save, carry-look ahead, ripple, are all different.
|
g*********s
发帖数: 1782 | 20 can we catch overflow?
【在 p***o 的大作中提到】
: You got lost ... Here is what your code looks like:
: input a, b;
: while (b != 0)
: {
: (s,c)=CSA(a,b,0);
: a=s, b=2*c;
: }
: output a;
: CSA ensures s+2c == a+b so the loop keeps a+b unchanged.
: The loop terminates since it eliminates bits in b from right.
|
