Отправлено: 27.11.14 13:00. Заголовок: Bitwise operators

Looking for some help with bitwise operators, I read the documentation and everything I could find about them but I don't really have a basic understanding on how to apply them properly.

Say I have this problem which is from a previous lab:

3. Nibbles A nibble is a group of 4 bits. Write a function that given an unsigned n

a) returns the value with the nibbles placed in reverse order

b) returns the value with the bits in each nibble reversed

Can somebody help me with a solution for it ? I don't really need the code commentated since I am confident I can read it, I just don't know how to write something like this.

 Отправлено: 27.11.14 13:31. Заголовок: It is not difficult ..

It is not difficult to write the first function if to place the result in other number that is to use operation reverse-copy. Here is a demonstrative program

I suppose that the function should be written in C.

 
 #include <stdio.h> 
  
 unsigned int reverse_nibbles( unsigned int x ) 
 { 
 	unsigned int y = 0; 
 	 
 	for ( size_t i = 0; i < 2 * sizeof( unsigned int ); i++ ) 
 	{ 
 		y <<= 4; 
 		y |= x & 0xF; 
 		x >>= 4; 
 	} 
 	 
 	return y; 
 } 
  
 int main(void)  
 { 
 	unsigned int x = 0x12345678; 
 	unsigned int y = reverse_nibbles( x ); 
 	 
 	printf( "%x\t%x\n", x , y ); 
 	 
 	return 0; 
 } 
 

The output is

 
 12345678	87654321 
 

 Отправлено: 27.11.14 14:34. Заголовок: Yes, C is the langua..

Yes, C is the language sorry for not mentioning it, I forgot.
Anyway, seems I need to ask some stuff about this part:

y <<= 4;
y |= x & 0xF;
x >>= 4;

First, we shift y 4 bits to the left, why do we need to do this every iteration ?
Then we OR y with the result of x & 0xF. 0xF is 1111 in binary so that means x remains unchanged since 1 with 1 is 1 and 0 with 1 is 0, but why exactly did we have to mask it with 0xF first ? Because in my head this doesn't change anything. Then y |= x means we reverse every bit of x, is that what happens ?
Then we right shift x by 4. In case of 0000 1000 (8, say it's stored as just 1 byte), wouldn't right shifting by 4 produce 0000 0000 ?
And why do you pass x as a hex value ?

One more thing, say we have x = 8 (1000 binary) and we want to print the binary representation of it. What I saw people do is shift left by 3 (let's forget about all those 0's in front) so we get 0000 and then compare it with 1 as lets' say x & 1 ? printf("1") :printf(" 0"). I understand that AND with 1 doesn't change anything but what value gets received from x & 1 and why is is evaluated to true/false ? Doesn't it change the whole bit sequence ?


I don't know why this stuff seems to be so hard to me, I think I don't get a basic concept here....

 Отправлено: 27.11.14 14:57. Заголовок: Taking into account ..

Taking into account that the initial value of x in the program if to print it in hex looks like

 
 12345678 
 

let's assume that y already contains the last digit of x that is y looks like

 
 00000008 
 

That to get the last digit of x x was shifted right at the end of the first iteration of the loop. That is we now have (before the second iteration of the loop)

 
 x: 01234567 
 y: 00000008 
 

Now that to append the current last digit of x that is 7 to y we need to shift left y

 
 y <<= 4 
 

Now y will look like

 
 00000080 
 

Then we need to extract this last digit of x. If binary operator & will be applied to x

 
 x & 0xF 
 

then the value of the expression will be

 
 00000007 
 

So we have

 
 00000080 <== the current value of y 
 00000007 <== the value of expression x & 0xF 
 

and the result will be

 
 00000080 
 |  
 00000007 
 ====== 
 00000087 <== y |= x & 0xF 
 

All will be repeated in the next iteration of the loop.

Try to do this yourself using a paper and pencil

 Отправлено: 27.11.14 15:11. Заголовок: So, basically, in yo..

So, basically, in your example, every number is a nibble actually, right ? Thanks for this, I think I got this part.

Could you give me some logic on this aswell ?

Say we have x = 8 (1000 binary) and we want to print the binary representation of it. What I saw people do is shift left by 3 (let's forget about all those 0's in front) so we get 0000 and then compare it with 1 as lets' say x & 1 ? printf("1") :printf(" 0"). I understand that AND with 1 doesn't change anything but what value gets received from x & 1 and why is is evaluated to true/false ? Doesn't it change the whole bit sequence ?

 Отправлено: 27.11.14 15:24. Заголовок: After shifting x = 0..

After shifting x = 0b1000 by three to the right we will get 0b0001 (not 0b0000).

The result of expression x & 1 (after shifiting x by 3 to the right) will be 0b0001. If x would be equal to 0b0000 then the result of expression x & 1 would be equal to 0b0000.

So to print binary representation of x that is equal to 0b1000 you could write the loop

 
 for ( size_t i = 4; i != 0; ) 
 { 
     printf( "&d", x >> --i ); 
 } 
 .

 Отправлено: 30.11.14 09:00. Заголовок: A straightforward ap..

A straightforward approach to the second function can look the following way

 
 unsigned int swap_nibbles( unsigned int x ) 
 { 
 	for ( unsigned int y = 0x0F; y; y <<= 4 ) 
 	{ 
 		unsigned int tmp = ( x & y ) << 4 ; 
 		x &= ~y; 
 		y <<= 4; 
 		tmp |= ( x & y ) >> 4; 
 		x &= ~y; 
 		x |= tmp; 
 	} 
 } 
 

Though it is not an elegant solution however it works.
Below a demonstrative program that uses the both functions.

 
 #include <stdio.h> 
  
 unsigned int reverse_nibbles( unsigned int x ) 
 { 
 	unsigned int y = 0; 
 	 
 	for ( size_t i = 0; i < 2 * sizeof( unsigned int ); i++ ) 
 	{ 
 		y <<= 4; 
 		y |= x & 0xF; 
 		x >>= 4; 
 	} 
 	 
 	return y; 
 } 
  
 unsigned int swap_nibbles( unsigned int x ) 
 { 
 	for ( unsigned int y = 0x0F; y; y <<= 4 ) 
 	{ 
 		unsigned int tmp = ( x & y ) << 4 ; 
 		x &= ~y; 
 		y <<= 4; 
 		tmp |= ( x & y ) >> 4; 
 		x &= ~y; 
 		x |= tmp; 
 	} 
 	 
 	return x; 
 } 
  
 int main(void)  
 { 
 	unsigned int x = 0x12345678; 
  
 	printf( "%x\t%x\n", x , reverse_nibbles( x ) ); 
 	printf( "%x\t%x\n", x , swap_nibbles( x ) ); 
 	 
 	 
 	return 0; 
 } 
 

The program output is

 
 12345678	87654321 
 12345678	21436587