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

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

• Bit Twiddling Hacks

Answer 2

unsigned char c;

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

Answer 3

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 4

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 5

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 6

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 7

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

Answer 8

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 9

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 10

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

Answer 11

/*swaping four bits*/
#include<stdio.h>

void printb(char a) {
    int i;
    for( i = 7; i >= 0; i--)
        printf("%d", (1 &  (a >> i)));
    printf("\n");
}

int swap4b(char a) {
    return ( ((a & 0xf0) >> 4) | ((a & 0x0f) << 4) );
}


int main()
{
    char a = 10;
    printb(a);
    a = swap4b(a);
    printb(a);
    return 0;
}

Answer 12

This is how you swap bits entirely, to change the bit endianess in a byte.

"iIn" is actually an integer because I'm using it to read from a file. I need the bits in an order where I can easily read them in order.

// swap bits
iIn = ((iIn>>4) & 0x0F) | ((iIn<<4) & 0xF0); // THIS is your solution here.
iIn = ((iIn>>2) & 0x33) | ((iIn<<2) & 0xCC);
iIn = ((iIn>>1) & 0x55) | ((iIn<<1) & 0xAA);

For swapping just two nibbles in a single byte, this is the most efficient way to do this, and it's probably faster than a lookup table in most situations.

I see a lot of people doing shifting, and forgetting to do the masking here. This is a problem when there is sign extension. If you have the type of unsigned char, it's fine since it's a unsigned 8 bit quantity, but it will fail with any other type.

The mask doesn't add overhead, with an unsigned char, the mask is implied anyhow, and any decent compiler will remove unnecessary code and has for 20 years.

Answer 13

Solution for generic n bits swapping between last and first. Not verified for case when total bits are less than 2n. here 7 is for char, take 31 for integer.

unsigned char swapNbitsFtoL(unsigned char num, char nbits)
{
    unsigned char u1 = 0;
    unsigned char u2 = 0;

    u1 = ~u1;
    u1 &= num;
    u1 = (u1 >> (7 - (nbits - 1))); /* Here nbits is number of n=bits so I have taken (nbits - 1). */

    u2 = ~u2;
    u2 &= num;
    u2 = (u2 << (7 - (nbits - 1))); /* Here nbits is number of n=bits so I have taken (nbits - 1). */

    u1 |= u2; /* u1 have first and last swapped n bits with */

    u2 = 0;
    u2 = ~u2;
    u2 = ((u2 >> (7 - (nbits - 1))) | (u2 << (7 - (nbits - 1))));
    bit_print(u2);
    u2 = ~u2;
    u2 &= num;

    return (u1 | u2);
}

Answer 14

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 15

#include <stdio.h>
#include <conio.h>
#include <math.h>
void main() { 
    int q,t,n,a[20],j,temp;
    int i=0;
    int s=0;
    int tp=0;
    clrscr();
    printf("\nenter the num\n");
    scanf("%d",&n);
    t=n;
    while(n>0) {
        a[i]=n%2;
        i++;
        n=n/2;
    }
    printf("\n\n");
    printf("num:%d\n",t);
    printf("number in binary format:");
    for(j=i-1;j>=0;j--) {
        printf("%d",a[j]);
    }
    printf("\n");
    temp=a[i-1];
    a[i-1]=a[0];
    a[0]=temp;
    printf("number in binary format wid reversed boundary bits:");
    for(j=i-1;j>=0;j--) {
        printf("%d",a[j]);
    }
    printf("\n");
    q=i-1;
    while(q>=0) {
        tp=pow(2,q);
        s=s+(tp*a[q]);
        q--;
    }
    printf("resulatnt number after reversing boundary bits:%d",s);
    printf("\n");
    getch();
}