CODEWITHSUNDEEP
cbit-manipulation
Riptyde4
Riptyde4

Reputation: 5460

How can i swap every 2 bits in a binary number?

I'm working on this programming project and part of it is to write a function with just bitwise operators that switches every two bits. I've come up with a comb sort of algorithm that accomplishes this but it only works for unsigned numbers, any ideas how I can get it to work with signed numbers as well? I'm completely stumped on this one. Heres what I have so far:

        // Mask 1 - For odd bits
    int a1 = 0xAA; a1 <<= 24;
    int a2 = 0xAA; a2 <<= 16;
    int a3 = 0xAA; a3 <<= 8;
    int a4 = 0xAA;
    int mask1 = a1 | a2 | a3 | a4;

    // Mask 2 - For even bits
    int b1 = 0x55; b1 <<= 24;
    int b2 = 0x55; b2 <<= 16;
    int b3 = 0x55; b3 <<= 8;
    int b4 = 0x55;
    int mask2 = b1 | b2 | b3 | b4;

    // Mask Results
    int odd = x & mask1;
    int even = x & mask2;

    int newNum = (odd >> 1) | (even << 1);

    return newNum;

The manual creation of the masks by or'ing variables together is because the only constants that can be used are between 0x00-0xFF.

Upvotes: 2

Views: 1312

Answers (4)

Aki Suihkonen
Aki Suihkonen

Reputation: 20027

Minimizing the operators and noticing the sign extension problem gives:

int odd = 0x55;
odd |= odd << 8;
odd |= odd << 16;

int newnum =   ((x & odd) << 1 )  // This is (sort of well defined)
             | ((x >> 1) & odd);  // this handles the sign extension without
                                  // additional & -operations

One remark though: bit twiddling should be generally applied to unsigned integers only.

Upvotes: 2

Floris
Floris

Reputation: 46365

Minimizing use of constants by working one byte at a time:

unsigned char* byte_p;
unsigned char byte;
int ii;
byte_p = &x;   
for(ii=0; ii<4; ii++) {
  byte = *byte_p;
  *byte_p = ((byte & 0xAA)>>1) | ((byte & 0x55) << 1);
  byte_p++;
}

Minimizing operations and keeping constants between 0x00 and 0xFF:

unsigned int comb = (0xAA << 8) + 0xAA;
comb += comb<<16;
newNum = ((x & comb) >> 1) | ((x & (comb >> 1)) << 1);

10 operations.

Just saw the comments above and realize this is implementing (more or less) some of the suggestions that @akisuihkonen made. So consider this a tip of the hat!

Upvotes: 0

Freddie
Freddie

Reputation: 891

When you right shift a signed number, the sign will also be extended. This is known as sign extension. Typically when you are dealing with bit shifting, you want to use unsigned numbers.

Upvotes: 0

Mark Ransom
Mark Ransom

Reputation: 308140

The problem is that odd >> 1 will sign extend with negative numbers. Simply do another and to eliminate the duplicated bit.

int newNum = ((odd >> 1) & mask2) | (even << 1);

Upvotes: 3

Related Questions