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??

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

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.

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???

'sizeof' returns the number of bytes. There are 8 bits per byte. This is why you multiply by eight.

Quzah.

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.

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.

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.

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)) );
}

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.

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)) );
}

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.

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.

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.

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.