optimizing bitwise operations

Question

I have a unsigned integer N = abcd where a,b,c,d represents bits from msb to lsb. I want get following numbers

x1 = ab0cd
x2 = ab1cd

What is the fastest way to do it using bitwise operations in C?

What I'm trying right now is as follows

unsigned int blockid1 = N>>offset;
unsigned int key1 = (blockid<<(1+offset))|(((1<<offset)-1)&N);
unsigned int key2 = (key1)|(1<<offset);

here offset is the location where I want to insert 0 and 1.

I'm guessing that bitwise operations are all constant time operations, so I don't know what would pass up as fasted bitwise operations. If what you have works, I don't know that there will be any faster way to do such things. These operations would map to CPU instructions in most cases anyways/ — Tony The Lion
– Tony The Lion, Commented Sep 17, 2012 at 8:38
is the offset always 2 ?, the position is always at the 3rd bit ?? — Rami Jarrar
– Rami Jarrar, Commented Sep 17, 2012 at 9:19

meh · Accepted Answer · 2012-09-22 16:33:33Z

1

const unsigned int mask = (~0) << offset;  // same as -(2**offset)
unsigned int key1 = N + (N & mask);
unsigned int key2 = key1 - mask;

answered Sep 22, 2012 at 16:33

meh

111 bronze badge

Sign up to request clarification or add additional context in comments.

Comments

unwind · Accepted Answer · 2012-09-17 08:39:00Z

0

Since your input is only 4 bits wide, which means there are a total of only 16 outputs, I would recommend at least testing (i.e. implementing and profiling) a look-up table.

These days, with super-fast ALUs and slow(ish) memories, look-ups are not often faster, but it's always worth testing. A small table means it won't pollute the cache very much, which might make it faster than a sequence of arithmetic instructions.

Since your outputs are pretty small too, the complete table could be represented as:

const static uint8_t keys[16][2];

32 bytes is very small, and if you do this often (i.e. many times in a row in a tight loop), the table should fit totally in cache.

answered Sep 17, 2012 at 8:39

unwind

402k64 gold badges492 silver badges620 bronze badges

1 Comment

arbitUser1401 Over a year ago

4 bit was just for example. numbers are regular 32 bit wide

Clement J. · Accepted Answer · 2012-09-17 08:56:59Z

0

You should have a look at Jasper Neumann's pages about bit permutations. It includes an online code generator. However it may be usefully complex for your specific case (permutation of one bit if we consider the 0 or 1 to be the MSB).

Note: I let you google the adresse since it has no domain name and direct IPs are not allowed by SO.

answered Sep 17, 2012 at 8:56

Clement J.

3,03228 silver badges30 bronze badges

1 Comment

user1724105 Over a year ago

My site about bit permutations and other stuff is and was always accessible via programming.sirrida.de but was redirected to a private server with a semistatic ip address. Since 2012-10-01 it is hosted on "real" web space. Jasper Neumann

Collectives™ on Stack Overflow

optimizing bitwise operations

3 Answers 3

Comments

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related