Swap bits in a number in C.

Question

In a C interview, I was asked to swap the first 4-bits of a number with the last 4 bit. (eg. 1011 1110 should be 1110 1011.)

Does anyone have a solution for this?

Answer 1

Just use a temporary variable and move the last bit into that variable, then shift the bit in that direction and end of masking in the bits in the tmp var and you are done.

---

Update: Let's add some code and then you can choose what is more readable.

The working one liner

unsigned int data = 0x7654;
data = (data ^ data & 0xff) | ((data & 0xf) << 4) | ((data & 0xf0) >> 4);
printf("data %x \n", data);

---

the same code but with some tmp vars

unsigned int data = 0x7654;

unsigned int tmp1 = 0;
unsigned int tmp2 = 0;

tmp1 = (0x0f&data)<<4;
tmp2 = (0xf0&data)>>4;
tmp1 = tmp1 | tmp2;

data = data ^ (data & 0xff); 

data = data | tmp1;

printf("data %x \n", data);

---

Well the one liner is shorter anyway :)

---

Update:

And if you look at the asm code that gcc generated with -Os -S, my guess is that they are more or less identical since the overhead is removed during the "compiler optimisation" part.

Answer 2

There's no need for a temporary variable, something like this should do it:

x = ((x & 0xf) << 4) | ((x & 0xf0) >> 4);

There is a potential pitfall with this depending on the exact type of x. Identification of this problem is left as an exercise for the reader.

Answer 3

unsigned char c;

c = ((c & 0xf0) >> 4) | ((c & 0x0f) << 4);

Answer 4

Are you looking for something more clever than standard bit-shifting?

(assuming a is an 8-bit type)

a = ((a >> 4) & 0xF) + ((a << 4) &0xF0)

Answer 5

C++-like pseudocode (can be easily rewritten to not use temporary variables):

int firstPart = source & 0xF;
int offsetToHigherPart = sizeof( source ) * CHAR_BIT - 4;
int secondPart = ( source >> offsetToHigherPart ) & 0xF;
int maskToSeparateMiddle = -1 & ( ~0xF ) & ( ~( 0xF << offsetToHigherPart );
int result = ( firstPart << offsetToHigherPart ) | secondPart | (source & maskToSeparateMiddle);

This will require CHAR_BIT to be defined. It is usually in limits.h and is defined as 8 bits but is strictly speaking platform-dependent and can be not defined at all in the headers.

Answer 6

x86 assembly:

asm{
  mov AL, 10111110b
  rol AL
  rol AL
  rol AL
  rol AL
}

http://www.geocities.com/SiliconValley/Park/3230/x86asm/asml1005.html

Answer 7

If you haven't seen or done much bit twiddling, a good resource to study is:

• Bit Twiddling Hacks

Answer 8

My skills in this area are new and therefore unproven so if I'm wrong then I learn something new, which is at least a part of the point of Stack Overflow.

Would a bitmask and XOR work also?

Like so?

var orginal=
var mask =00001110 //I may have the mask wrong
var value=1011 1110
var result=value^mask;

I might be misunderstanding things, forgive me if I've screwed up entriely.

Answer 9

There is no "correct answer" to this kind of interview question. There are several ways to do this (lookup tables, anyone?) and the tradeoffs between each way (readability vs. performance vs. portability vs. maintainability) would need to be discussed.

The question is just an opening gambit to get you discussing some of the above issues, and to determine how 'deeply' you can discuss such problems.

Answer 10

unsigned char b;
b = (b << 4) | (b >> 4);

Answer 11

The easiest is (t is unsigned):

t = (t>>4)|(t<<4);

But if you want to obfuscate your code, or to swap other bits combination you can use this base:

mask = 0x0F & (t ^ (t >> 4));
t ^= (mask | (mask << 4));