CODEWITHSUNDEEP
cbit-manipulation
zyg1990
zyg1990

Reputation: 11

Switching bits in each nibble of an int

How can I switch the 0th and 3rd bits of each nibble in an integer using only bit operations (no control structures)? What kind of masks do I need to create in order to solve this problem? Any help would be appreciated. For example, 8(1000) become 1(0001). 

/* 
 * SwitchBits(0) = 0
 * SwitchBits(8) = 1
 * SwitchBits(0x812) = 0x182
 * SwitchBits(0x12345678) = 0x82a4c6e1
 * Legal Operations: ! ~ & ^ | + << >>
 */
int SwitchBits(int n) { 

}

Upvotes: 1

Views: 525

Answers (5)

Apriori
Apriori

Reputation: 2306

  1. Move the low bits to the high bits and mask out the resulting bits.
  2. Move the high bits to the low bits and mask out the resulting bits.
  3. Mask out all bits that have not been moved.
  4. Combine the results with ORs.

Code:

unsigned SwitchBits(unsigned n) {
  return ((n << 3) & 0x88888888) | ((n >> 3) & 0x11111111) | (n & 0x66666666);
}

Alternativly, if you would like to be very clever. It can be done with two fewer operations, though this may not actually be faster due to some of the dependicies between instrutions.

  1. Move the high bits to align with the low bits
  2. XOR recording a 0 in the low bit if high an low bits are the same, and a 1 if they are different.
  3. From this, mask out only the low bit of each nibble.
  4. From this, multiply by 9, this will keep the low bit as is, and also copy it to the high bit.
  5. From this, XOR with the original value. in the case that the high and low bit are the same, no change will correctly occure. In the case they are different, they will be effectivly exchanged.

Code:

unsigned SwitchBits(unsigned n) {
  return ((((n >> 3) ^ n) & 0x11111111) * 0x9) ^ n;
}

Upvotes: 1

Steve Cox
Steve Cox

Reputation: 2007

Try this variant of the xor swap:

uint32_t switch_bits(uint32_t a){
  static const mask = 0x11111111;
  a ^= (a & mask) << 3;
  a ^= (a >> 3) & mask;
  a ^= (a & mask) << 3;
  return a;
}

Upvotes: 1

vinay hunachyal
vinay hunachyal

Reputation: 3901

Try below code . Here you should know bitwise operator to implement and correct position to place.Also needs to aware of maintenance ,shifting and toggling basic properties.

 #include<stdio.h>
 #define BITS_SWAP(x) x=(((x & 0x88888888)>>3) | ((x & 0x11111111)<<3)) | ((x & ~ (0x88888888 | 0x11111111)))

 int main()
 {
    int data=0;
    printf("enter the data in hex=0x");
    scanf("%x",&data);
    printf("bits=%x",BITS_SWAP(data));
    return 0;
 }

OP

vinay@vinay-VirtualBox:~/c_skill$ ./a.out

enter the data in hex=0x1

bits=8

vinay@vinay-VirtualBox:~/c_skill$ ./a.out

enter the data in hex=0x812 bits=182

vinay@vinay-VirtualBox:~/c_skill$ ./a.out

enter the data in hex=0x12345678 bits=82a4c6e1

vinay@vinay-VirtualBox:~/c_skill$

Upvotes: 1

Thanatos
Thanatos

Reputation: 44334

To obtain a bit, you can mask it out using AND. To get the lowest bit, for example:

x & 0x01

Think about how AND works: both bits must be set. Since we're ANDing with 1, all bits except the first must be 0, because they're 0 in 0x01. The lowest bit will be either 0 or 1, depending on what's in x; said differently, the lowest bit will be the lowest bit in x, which is what we want. Visually:

    x = abcd
AND 1 = 0001
    --------
        000d

(where abcd represent the bits in those slots; we don't know what they are)

To move it to bit 3's position, just shift it:

(x & 0x01) << 3

Visually, again:

x & 0x01 = 000d
    << 3
    -----------
           d000

To add it in, first, we need to clear out that spot in x for our bit. We use AND again:

x & ~0x08

Here, we invert 0x08 (which is 1000 in binary): this means all bits except bit 3 are set, and when we AND that with x, we get x except for that bit.

Visually,

 0x08 = 1000
(invert)
-----------
        0111
AND x = abcd
------------
        0bcd

Combine with OR:

(x & ~0x08) | ((x & 0x01) << 3)

Visually,

          x & ~0x08 = 0bcd
| ((x & 0x01) << 3) = d000
--------------------------
                      dbcd

Now, this only moves bit 0 to bit 3, and just overwrites bit 3. We still need to do bit 3 → 0. That's simply another:

x & 0x08 >> 3

And we need to clear out its spot:

x & ~0x01

We can combine the two clearing pieces:

x & ~0x09

And then:

(x & ~0x09) | ((x & 0x01) << 3) | ((x & 0x08) >> 3)

That of course handles only the lowest nibble. I'll leave the others as an exercise.

Upvotes: 1

Jonathan Leffler
Jonathan Leffler

Reputation: 754530

Code:

#include <stdio.h>
#include <inttypes.h>

static uint32_t SwitchBits(uint32_t n)
{
    uint32_t bit0_mask = 0x11111111;
    uint32_t bit3_mask = 0x88888888;
    uint32_t v_bit0 = n & bit0_mask;
    uint32_t v_bit3 = n & bit3_mask;
    n &= ~(bit0_mask | bit3_mask);
    n |= (v_bit0 << 3) | (v_bit3 >> 3);
    return n;
}

int main(void)
{
    uint32_t i_values[] = { 0, 8, 0x812, 0x12345678, 0x9ABCDEF0 };
    uint32_t o_values[] = { 0, 1, 0x182, 0x82A4C6E1, 0x93B5D7F0 };
    enum { N_VALUES = sizeof(o_values) / sizeof(o_values[0]) };

    for (int i = 0; i < N_VALUES; i++)
    {
        printf("0x%.8" PRIX32 " => 0x%.8" PRIX32 " (vs 0x%.8" PRIX32 ")\n",
                i_values[i], SwitchBits(i_values[i]), o_values[i]);
    }
    return 0;
}

Output:

0x00000000 => 0x00000000 (vs 0x00000000)
0x00000008 => 0x00000001 (vs 0x00000001)
0x00000812 => 0x00000182 (vs 0x00000182)
0x12345678 => 0x82A4C6E1 (vs 0x82A4C6E1)
0x9ABCDEF0 => 0x93B5D7F0 (vs 0x93B5D7F0)

Note the use of uint32_t to avoid undefined behaviour with sign bits in signed integers.

Upvotes: 2

Related Questions