Thread: pseudocode bit level help

  1. #1
    Registered User
    Join Date
    Feb 2013
    Posts
    13

    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?
    5 Set output[4] = 1 why did we jump to output4?
    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

  2. #2
    Registered User
    Join Date
    Feb 2013
    Posts
    13
    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)

  3. #3
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    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.
    Devoted my life to programming...

  4. #4
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    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.
    Devoted my life to programming...

  5. #5
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    if it was C++ it would do something like:
    Code:
    output = ((b >> 1) | 0x8) & ~a;
    but I still don't understand its purpose!
    Devoted my life to programming...

  6. #6
    Registered User
    Join Date
    Feb 2013
    Posts
    13
    this is the only extra information...
    Trace through the algorithm for input a = 0011, b = 1010. Specifically,
    (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.

  7. #7
    Registered User
    Join Date
    Feb 2013
    Posts
    13
    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

  8. #8
    Registered User
    Join Date
    Feb 2013
    Posts
    13
    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?

  9. #9
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    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)
    Devoted my life to programming...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Pseudocode help
    By oliversacks in forum Tech Board
    Replies: 13
    Last Post: 02-06-2013, 11:16 AM
  2. pseudocode help
    By dantheman4 in forum Tech Board
    Replies: 3
    Last Post: 09-29-2011, 06:19 PM
  3. Pseudocode ?
    By sarajko in forum C Programming
    Replies: 1
    Last Post: 11-19-2010, 06:40 AM
  4. pseudocode
    By samsung in forum C Programming
    Replies: 8
    Last Post: 10-28-2007, 12:46 PM
  5. help with pseudocode?
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 08-11-2002, 06:33 PM