bitwise shifts

This is a discussion on bitwise shifts within the C Programming forums, part of the General Programming Boards category; not exactly understanding the function described here: Write following function: Code: unsigned int rotate_left(unsigned int i, int n); /* prototype ...

  1. #1
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157

    bitwise shifts

    not exactly understanding the function described here:

    Write following function:

    Code:
    unsigned int rotate_left(unsigned int i, int n);   /* prototype *
    Its value should be the result of shifting the bits in i to the left by n places, with the bits that were "shifted off" moved to the right end of i.

    Ex. the call rotate_left(0x1234,4) should return 0x2341, if integers are 16bits long.

    What I am not understanding is how do I access the "bits" and shift these values around??

    for example, a 16bit code could be 0453A678B123C456 and shifting 5 to left would return 0678B123C456453A Right???
    the leading zero is always 0, as that is what I understood to be the bit designating the sign of the whole "string" of numbers
    0 = positive
    1 = negative

    If this return I have listed is correct, then do you access the bits by a simple expression?? All we played around with in understanding the logic is an expression like

    i = i << 2; or i =<< 2;
    j = j >> 5; or j =>> 5;

    does the following code work in bit shifting??

    [code]
    unsigned int rotate_left(unsigned int i, int n)
    {

    i =<<n;
    }

    This doesn't look right compared to similar examples in book. I am stumped with the bitwise operators needed to access bits..to set, clear and test a bit.

    Anyone got any good examples to help me??
    Sue B.

    dazed and confused


  2. #2
    Registered User
    Join Date
    Aug 2001
    Posts
    6
    for a start, if the number is 'unsigned' then the leftmost bit is not used to determine the sign of the integer, as it is unsigned.

    another thing to be cautious of, is that the size of an integer is variable depending on the hardware/compiler that you are using. the ANSI spec simply states that an integer value must be at least 16 bits. the spec does not state what the maximum value can be however

    the following function should work:


    unsigned int rotate_left(unsigned int i, int n)
    {
    return ( (i << n) | (i >> ((sizeof(int)*8)-n)) );
    }


    NB if a 'signed' integer was used in the above function, the result would be incorrect, as the right shift would result in a value with leftmost 1's where the shifting had taken place, when this is subsequently OR'd with the left shift value, the final value would be incorrect

  3. #3
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    not gonna show you how to do it but i will give you some pointers.....

    TRUTH TABLES
    Code:
    A     B     A&B
    0     0       0
    0     1       0
    1     0       0
    1     1       1
    As you can see anything 'anded' with 0 is 0. Useful for clearing bits. 'anding' with 1 can be used as a bit test. The table above shows how this works.
    Code:
    A     B     A|B
    0     0      0
    0     1      1
    1     0      1
    1     1      1
    As you can see here anything 'ored' with 1 is 1 so this can be used to set bits.
    Code:
    A     B     A^B
    0     0       0
    0     1       1
    1     0       1
    1     1       0
    This is 'xoring'. This is useful for toggling bits.

    while looking at these there is also this one.... ~ the one's complement operator.
    Code:
    A      ~A
    0        1
    1        0
    This just inverts bits.

    now to shifting.....

    assuming an unsigned char for clarity.....

    given this bit pattern...... 00110011
    a single shift left gives 01100110
    note two things.... firstly the second number is the first number * 2. secondly the bit on the left is not the zero rotated around from the most significant byte.That zero is lost.

    going back to the first bit pattern 00110011
    a single shift right gives 00011001
    again note that this is half of the first value and that the zero added in the most significant byte is not the zero rotated around from the least significant byte.
    With right shifts and signed values the padding depends on the sign bit. if negative padding will be 1 not zero to preserve the sign bit.

    you now have to implement a signed 16 bit rotate. There is enough info here for you to come back with some code now...

    btw. there is a quick cheat if you know assembly language and how to inline it but that defeats the purpose.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  4. #4
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157
    Why does the following code work??

    Code:
    unsigned int rotate_left(unsigned int i, int n) 
    { 
    return ( (i << n) | (i >> ((sizeof(int)*8)-n)) ); 
    }

    why ( i >> ((sizeof(int)*8)-n)) ??

    why multiply by 8 ??

    Instructor lecture explained that you can take 16-bit and break into 4 parts and treat each part as a binary.

    ex. 0000001100101011 (binary)

    is the same as

    0 3 2 11

    written in hex =
    0 3 2 B or 0x032B

    If this is true, where's the 8 coming from in the above code you wrote???
    Last edited by sballew; 11-26-2001 at 09:38 PM.
    Sue B.

    dazed and confused


  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    'sizeof' returns the number of bytes. There are 8 bits per byte. This is why you multiply by eight.

    Quzah.
    Hope is the first step on the road to disappointment.

  6. #6
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157
    ok 8 bits per byte, i forgot that part; so 16 bits is 2 bytes

    Now back to the function Oscar gave:

    Code:
    unsigned int rotate_left(unsigned int i, int n) 
    { 
    return ( (i << n) | (i >> ((sizeof(int)*8)-n)) ); 
    }
    I think I don't get what the expressions mean.

    (i << n) this means shift to the left "n" bits???
    "n" being passed to the function

    (i >> ((sizeof(int)*8)-n)) this means shift to the right by
    one byte less the value of
    of "n" ???

    How is this evaluated with the OR in the full return 'expression' in parentheses??

    I am not following how this is moving n bits to the left and taking those bits on the left end and moving to the right end; that was what was demonstrated to be the result after call of the function, per instructions.

    Its value should be the result of shifting the bits in i to the left by n places, with the bits that were "shifted off" moved to the right end of i.

    Ex. the call rotate_left(0x1234,4) should return 0x2341, if integers are 16bits long.
    Sue B.

    dazed and confused


  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Look at the truth tables as given to you, above.

    Remember that when you "or" something, you can use it to "set" a value. Thus, if we have this bit pattern:

    01100111

    And we apply it to this function, with N being 3...

    Shifted left 3 times:

    00111000

    Shifted right 5 times:

    00000011

    Or them:

    00111011

    Thus, you end up with what would happen if you had "rotated" the bit to the left three places.

    Quzah.
    Hope is the first step on the road to disappointment.

  8. #8
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    Umm.. I know this doesn't have much to do with how to rotate numbers, but this is the kind of thing where if you don't already know how to do it, you probably need a function to print a number in binary form...
    Code:
    int main()
    {
     int i, rotation;
     
     for (i = 1; i != 0; )
     {
      printf ("\nGimme number and rotation.\n");
      scanf("%d %d", &i, &rotation);
      printf ("\nOriginal Number:\n");
      pBinary (i);
      printf ("\nRotated Number:\n");
      pBinary (rotateLeft (i, rotation));
     }
     return 0;
    }
    I get the feeling that a bit of visualization is really all it takes to figure out this kinda problem. Printing numbers in binary is a problem that you could probably do, but just for the heck of it, here's a version of pBinary.
    Code:
    void pBinary (int i)
    {
     int mask;
     for (mask = 0x8000; mask != 0; mask >>= 1)
     {
      if (mask & i) printf ("1");
      else printf ("0");
     }
     return;
    }
    As usuall, no promises that anything I write will work. And everyone here's pretty much posted what you have to do.. you've gotta shift it right, take those bits, or 'm with some bits shifted left, and viola, the answer.
    Callou collei we'll code the way
    Of prime numbers and pings!

  9. #9
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157
    Ok, I am not getting anywhere with the following code. Please help.

    I vaguely understand the AND , OR and XOR operators but
    I am not getting what I need for a result

    if I input the following values when prompted:

    1234567890 5 (shift 5 to left)

    I am getting the following output :

    851466825

    What is wrong??

    [code]


    #include <stdio.h>

    unsigned int rotate_left(unsigned int i, int n);

    main()
    {

    int number,shifter;


    printf ("Enter integers and a value to shift them to "
    "the left by (separaated by single space): ");
    scanf("%d %d",&number,&shifter);

    printf("Your original number was %d\n"
    "And it was shifted %d places to the left\n"
    "Now results in the number %d\n\n",
    number,shifter,rotate_left(number,shifter));

    return 0;

    }

    unsigned int rotate_left(unsigned int i, int n)
    {
    return ( (i << n) | (i >> ((sizeof(int)*8)-n)) );
    }
    Sue B.

    dazed and confused


  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    if I input the following values when prompted:

    1234567890 5 (shift 5 to left)

    I am getting the following output :

    851466825

    What is wrong??
    Probably nothing. You're shifting BITS, not CHARACTERS. Use the provided code, and print the bit pattern of the value, not the value itself.

    Quzah.
    Hope is the first step on the road to disappointment.

  11. #11
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157
    I am not quite sure about this code.
    I seem to have some problem understanding what the result should look like.

    If I input a base-10 number like
    1028

    that should yield a binary number
    10000000000
    (2 ^10)

    Right??

    in hex that would be 0000 0100 0000 0000 Right?

    The largest base-10 to binary number would be
    less than 100000

    So how come my answer is showing after a shift a number bigger than 100000???

    Forgive my stupidity. This is by far the hardest thing I have tried to imagine, since my brain is used to base-10 format of numbers. Been a very long time that I talked in binary.

    here's what I got now:

    Code:
    #include <stdio.h>
    
    unsigned int rotate_left(unsigned int i, int n);
    
    main()
    {
    
       int number,shifter;
       int i;
    
        printf ("Enter integers and a value to shift them to "
               "the left by (separaated by single space):  ");
        scanf("%d %d",&number,&shifter);
    
        printf("Your original number was %d\n"
               "And it was shifted %d places to the left\n",
               number,shifter);
        i=rotate_left(number,shifter);
        printf("\nNow results in the number %d \n\n",i);
    
        return 0;
    
    }
    
    unsigned int rotate_left(unsigned int i, int n)
    {
      int mask;
      for (mask = 0x8000; mask != 0; mask >>=1)
     {
      if (mask & i) printf ("1");
      else printf ("0");
     }
    
      return ( (i << n) | (i >> ((sizeof(int)*8)-n)) );
    }
    Sue B.

    dazed and confused


  12. #12
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    A 32 bit integer can have a "base 10" number, unsigned, of ~4 billion. Signed, ~2 billion. A 16 bit integer, unsigned, is roughly 65000, and signed, is roughly 32000.

    Use the function provided by QuestionC to display how each bit looks, then you can call it before and after you shift, and you'll see what we're trying to show you.

    Quzah.
    Hope is the first step on the road to disappointment.

  13. #13
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    To tell you the truth, there isn't much point in trying to think of numbers when dealing with bit-shifts. If you ever end up using bit-wise operators in real life, it's probably going to be something a bit more direct, like having to write to a file one bit at a time.

    In all likelyhood, your int is bigger than 16 bits. There isn't any standard size limit on the size of an int, just a minimum size. Since computers nowadays are pretty much all 32-bit, compilers almost always use something like 32-bit integers by default, so your max int is going to be something gargantuan.

    So, if you want to limit your shifts to just 16-bit registers, you'll have to clip your ints before you return from rotate_left with this line...
    i &= 0xFF;

    I think there was a misunderstanding about the code I posted.. it wasn't really a solution at all, it is just debugging code...
    Code:
    #include <stdio.h>
    
    void pBinary (int i);
    int rotate_left (unsigned int i, int n);
    
    int main()
    {
     int i, rotation;
     
     for (i = 1; i != 0; )
     {
      printf ("\nGimme number and rotation.\n");
      scanf("%d %d", &i, &rotation);
      printf ("\nOriginal Number:\n");
      pBinary (i);
      i = rotate_left (i, rotation);
      printf ("\nRotated Number:\n");
      pBinary (i);
     }
     return 0;
    }
    
    void pBinary (int i)
    {
     int mask;
     for (mask = 0x8000; mask != 0; mask >>= 1)
     {
      if (mask & i) printf ("1");
      else printf ("0");
     }
     return;
    }
    
    rotate_left (unsigned int i, int n)
    {
     // Space for rent
    }
    Seriously, just copy and paste that code, and supply your own code for rotate_left. pBinary will only print the last 16 bits of the int, so if you have problems associated with ints being larger than 16 bits, this program will not help to detect that, but otherwise it should do well I hope.

    oscar's code isn't incorrect, but this program will not work with the code he posted anyhow, so you're going to have to rewrite that from scratch. Hopefully this program will help.
    Callou collei we'll code the way
    Of prime numbers and pings!

  14. #14
    Sayeh
    Guest
    Okay, let's cut through the junk and (hopefully) provide a straightforward explanation with examples that make sense.

    First of all, you have to understand how the number correlate to one another, decimal, binary, and hex. forget thinking in bases (base 10, base 2, base 16). This is accurate but pointless-- you want to _visualize_ what's going on--

    Also, let's work with numbers you can fit in your head--

    55, 76, 23, 10, 19... not 123479, or 77881239, or 09193882.

    The principles apply, no matter what size the number.

    ---

    To start, let's look at decimal, hex, and binary conversions.

    Whenever you left shift, you are multiplying by 2. Whenever you rightshift, you are dividing by 2. (powers of 2).

    An 8-bit binary number looks like this:

    1010 1010

    Each bit has a different value. If it's 0, the value isn't added. If it's a 1, the corresponding value is added.

    If the MSB (most significant bit) is on the left-- that means the bit position that is worth the most-- an 8-bit number has each bit valued as follows:

    128 64 32 16 8 4 2 1
    -----------------------------------

    If you were to add these numbers up, you would get a value of 256d -- the largest positive value a byte (or an unsigned char) can hold.

    If we take the above binary, and match it's values to the corresponding bit-values, we find that it is equivalent to the following:

    1 0 1 0 1 0 1 0
    -----------------------------------------------------------
    128+ 0+ 32+ 0+ 8+ 0+ 2+ 0 = 170d

    Now, understand that hex is very easy to correspond to binary, because each hex digit is equivalent to 4-bits (called a nybble). Hex values correspond to binary as follows, and are only added in 4-bit chunks. Like so:

    1 0 1 0 1 0 1 0
    -----------------------------------------------------------
    8+ 0+ 2+ 0 8+ 0+ 2+ 0 = 0xAA


    Since each nybble can represent 4-bits, or 16 values (0-15), you can't use multi-digit numbers like 10, 11, 12, etc. The number would be sloppy and not understandable. Hex, however, uses letters in please of multi-digit numbers. Like so:

    0-9, and A-F = hex
    ------------------
    0-9, and 10-15 = decimal
    ------------------
    0000 - 1111 = binary

    In the above example, 10101010 in binary can't be represented by 0x1010 in hex... that' wouldn't be right at all! Instead, hex numbers are 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E, and F. Since each nybble (1010 in binary) is worth 10d... it converts to the letter 'A' in hex. Or more correctly 0xA.

    ---

    So in the end, 10101010 = 170d = 0xAA.

    ---

    Now-- let's look at '55d' again, so we can discuss shifting (multiplying by 2). As you learned above, each bit has a particular value associated with it, whether it's in binary or hex. Because of that, if you shift bits, the corresponding values don't move with the shift, each bit just equals a different value-- Note the example:

    55 = 0x37 = 0011 0111

    Again (using 8,4,2,1), 0x37 = 0+ 0+ 32+ 16+ 0 + 4+ 2+ 1 = 55.

    If we left-shift 55 by 1 bit (in C that is: 55 << 1), we get the following value:

    0110 1110 = 0x6E

    The CPU automatically stuffs a new zero in on the right end, and pushes the leftmost bit right off into the void.

    If we again break the binary down to bit values, we see that the new binary number converts to decimal as follows:

    0 1 1 0 1 1 1 0
    -------------------------------------------------------------
    0+ 64+ 32+ 0+ 8+ 4+ 2+ 0 = 110d

    or in hex:

    0 1 1 0 1 1 1 0
    -------------------------------------------------------------
    0+ 4+ 2+ 0+ 8+ 4+ 2+ 0 = 0x6E

    *****************

    Okay, so back to one of your basic questions--

    Why didn't this work?

    ---------------------
    1234567890 5 (shift 5 to left)

    I am getting the following output :

    851466825

    What is wrong??
    ----------------------

    Well, the simple answer is that by multiplying 1234567890 * 2, 5 times in a row, you created a value larger than what the processor could handle. It pushed significant bits off the left end of the register and lost them. Here's what the binary looked like:

    0100 1001 1001 0110 0000 0010 1101 0010

    That is 1,234,567,890 in binary. Take a look at the MSB (bits worth the most on the left end)... if you shift left 5 times, you lose 0100 1.

    You can write out on paper what those two positive bits are worth... a lot! starting from the left, the values are (I won't cover the whole binary number):

    0+ 1,073,741,824+ 0+ 0+ 134,217,728+ 0+ 0+ .... and so on.

    The binary becomes:

    0011 0010 1100 0000 0101 1010 0100 0000

    or 851,466,816 in decimal.

    The fact that you say you got '851,466,825 ' shows either an additional rounding error with your compiler, or a typo.

    enjoy.

  15. #15
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    0011 0010 1100 0000 0101 1010 0100 0000

    or 851,466,816 in decimal.

    The fact that you say you got '851,466,825 ' shows either an additional rounding error with your compiler, or a typo.

    enjoy.
    No, here is their end result, and how they get it, with a little proggie i threw together:
    Code:
    #include <stdio.h>
    
    void printbits( int x )
    { int y;
    	for( y = 0; y < 32; y++ ) printf("%d",(x&(1<<y))?1:0);
    	printf("\n");
    }
    
    int rotatebits( int i, int n )
    {
    	return ( (i << n) | (i >> ((sizeof(int)*8)-n)) );
    }
    
    int main( void )
    {
    	int x = 1234567890;
    	
    	printbits( x );
    	x = rotatebits( x, 5 );
    	printbits( x );
    	printf("%d", x );
    	return 0;
    }
    Output is:

    01001011010000000110100110010010
    10010010010110100000001101001100
    851466825

    Quzah.
    Hope is the first step on the road to disappointment.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bitwise Questions
    By someprogr in forum C Programming
    Replies: 8
    Last Post: 12-14-2008, 06:45 PM
  2. Bitwise Shift Operations
    By John_L in forum Tech Board
    Replies: 19
    Last Post: 02-25-2008, 11:22 AM
  3. bitwise operations with double
    By henry_kay in forum C Programming
    Replies: 2
    Last Post: 10-03-2007, 05:57 AM
  4. C bitwise operator exercise - more like newb killer
    By shdwsclan in forum C Programming
    Replies: 3
    Last Post: 02-22-2006, 07:02 AM
  5. Characters into bitwise ints
    By Code Zer0 in forum C++ Programming
    Replies: 9
    Last Post: 04-24-2003, 09:34 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21