# pseudocode bit level help

• 02-20-2013
oliversacks
pseudocode bit level help
I know this is a section devoted to C++ programming but I hope my question is ok...
I am having a lot of trouble understanding pseudocode algorithms in my intro Comp Sci class. I understand what while, set etc means but the way my prof uses the variables (i.e., i=1, [I]output = b[i + 1] etc) confuses me way too much. Here is the algorithm:
i'll put my comments in bold
input: two 4-bit binary strings a (0011) and b (1010)
output: one 4-bit binary string output
1 Set i = 1 this is a control variable to limit us to 4 movements?
2 while i<4 so while we are under 4 moves right, we do the following?
3 [I]output= b[i + 1] output is italicized like in instructions at top, so this line is giving me the first digit for the single 4-bit string in our final output correct? is this first loop only concerned with the b string? is nothing being considered in the a string yet?

4 Set i = i + 1 now we move onto the next process?
6 Set i = 1 why are we putting i back to 1??
7 while i <= 4
8 [I]output= [I]output AND (NOT(a[i])) which ith are they talking about in the two outputs? and which a[i] are they talking about?
9 Set i = i + 1
10 Set tmp = output[4] I really have no idea what this means
11 Set output[4] = output[3] nor do i get why we go back and forth between 3 and 4
12 Set output[3] = tmp
13 Print output

So that is it... This is what I understand of it or at least what I think I understand of it... I am not a comp sci major but I really want to understand this stuff. I am not the only one in the class struggling like this... the prof is nice but he really really does not explain stuff very well. He kind of assumes everyone already gets it and does not go into detail. The lecture is invaded by 1000 questions constantly and I have been learning more researching on youtube and google than in the class. We also have no textbook so I have nothing to refer to for questions on these weird pseudocode algorithms
• 02-20-2013
oliversacks
the formatting didn't hold when i posted.. lines 3-4, 8-9 are indented... line 8 should have italics for output[i] (which is also written backwards somehow)
• 02-20-2013
GReaper
Do you happen to know the name of this algorithm, or at least what the output's supposed to represent?

Please use code tags to avoid such indentation problems in the future.
• 02-20-2013
GReaper
Let's expand the loops and iterate through the process:
Code:

```a = 0011 b = 1010 i = 1 output[1] = b[2] = 1 i = 2 output[2] = b[3] = 0 i = 3 output[3] = b[4] = 1 i = 4 output[4] = 1 i = 1 output[1] = output[1] AND (NOT a[1]) = 1 AND (NOT 1) = 0 i = 2 output[2] = output[2] AND (NOT a[2]) = 0 AND (NOT 1) = 0 i = 3 output[3] = output[3] AND (NOT a[3]) = 1 AND (NOT 0) = 1 i = 4 output[4] = output[4] AND (NOT a[4]) = 1 AND (NOT 0) = 1 i = 5 // This three lines exchange the contents of output[3] & output[4] tmp = output[4] = 1 output[4] = output[3] = 1 output[3] = tmp = 1 PRINT 1100```
Is it more clear now? Note that I read binary strings from right to left.
• 02-20-2013
GReaper
if it was C++ it would do something like:
Code:

`output = ((b >> 1) | 0x8) & ~a;`
but I still don't understand its purpose!
• 02-20-2013
oliversacks
this is the only extra information...
Trace through the algorithm for input a = 0011, b = 1010. Speciﬁcally,
(a) show the values of i and output immediately before each time Line 4 is executed, (b)
show the values of i and output immediately before each time Line 9 is executed, and (c)
show what is printed. In part (a), if a variable is not yet assigned a value when Line 4 is
executed, leave the value for that variable blank.
• 02-20-2013
oliversacks
and it is stated in the assignment to read left to right but it is easy to translate your answers to see what it means
• 02-20-2013
oliversacks
so this...
output[1] = output[1] AND (NOT a[1]) = 1 AND (NOT 1) = 0
i = 2
output[2] = output[2] AND (NOT a[2]) = 0 AND (NOT 1) = 0
i = 3
output[3] = output[3] AND (NOT a[3]) = 1 AND (NOT 0) = 1
i = 4
output[4] = output[4] AND (NOT a[4]) = 1 AND (NOT 0) = 1

the process is like a NOT gate or a NAND gate? in the final binary string output[3] for example is the opposite of a[3]? if a[3] were 1 then output[3] would be 0?
• 02-21-2013
GReaper
Actually "a NAND b" equals "NOT(a AND b)", so this isn't one.

A generalisation of post #5:
Code:

`output = ((b RSHIFT 1) OR 1000₂) AND (NOT a)`