CODEWITHSUNDEEP
assemblyx86
user1157549
user1157549

Reputation: 71

Swap bits (or just access them) in assembly x86

I'm going to come out with a disclaimer and say this is my homework problem. So I don't necessarily want you to solve it, I just want some clarification.

The exact problem is this:

Write a function to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, and so on).

It also hints that no conditional statements are required.

I kind of looked into it and I discovered if I somehow separate the even and odd bits I can use shifts to accomplish this. What I don't understand is how to manipulate individual bits. In python (programming language I'm used to) it's easy with the index operator as you can just do number[0] for example and you can get the first bit. How do you do something like this for assembly?

EDIT: So @jotik, thanks for your help. I implemented something like this:

mov edi, ebx
and edi, 0x5555555555555555
shl edi, 1
mov esi, ebx
and esi, 0xAAAAAAAAAAAAAAAA
shr esi, 1
or edi, esi
mov eax, edi

And when I saw the | operator, I was thinking OR was ||. Silly mistake.

Upvotes: 2

Views: 5433

Answers (2)

jotik
jotik

Reputation: 17900

In assembly one can use bit masks together with other bitwise operations to archive your result.

result = ((odd-bit-mask & input) << 1) | ((even-bit-mask & input) >> 1)

where odd-bit-mask is a value with all odd bits set (1) and even bits unset (0); and even-bit-mask is a value with all even bits set (1) and odd bits unset. For 64-bit values, the odd and even bit masks would be (in hexadecimal notation) 0x0x5555555555555555 and 0xAAAAAAAAAAAAAAAA respectively.

So the pseudocode of your assembly algorithm would probably look similar to the following:

oddbits  = input & 0x5555555555555555
oddbits  = oddbits << 1
evenbits = input & 0xAAAAAAAAAAAAAAAA
evenbits = evenbits >> 1
result   = oddbits | evenbits

where & is a bitwise AND operation, | is a bitwise OR operation, << and >> are the bitwise shift left and bitwise shift right operations respectively.

PS: You can find some other useful bit manipulation tricks on Sean Eron Anderson's Bit Twiddling Hacks webpage.

Upvotes: 4

datenwolf
datenwolf

Reputation: 162164

Here are a few hints:

  • Bitwise boolean operations (these usually have 1:1 counterparts in assembly, but if everything else fails, you can construct them by cleverly combining several XOR calls)

    • bitwise AND: 0b10110101 & 0b00011000 → 0b00010000
    • bitwise OR: 0b10110101 & 0b00011000 → 0b10111101
    • bitwise XOR: 0b10110101 & 0b00011000 → 0b10101101

  • Bit shifts

    • shift x by n bits to the left (x << n): 0b00100001 << 3 → 0b00001000
    • shift x by n bits to the right (x >> n): 0b00100001 >> 3 → 0b00000100

There's also rotating bit shift, where bits "shifted out" appear on the other side, but this is not as widely supported in hardware.

Upvotes: 1

Related Questions