Manipulating bits in C. Is there a better way?

Question

I have a program that uses the following two functions 99.9999% of time:

unsigned int getBit(unsigned char *byte, unsigned int bitPosition)
{
    return (*byte & (1 << bitPosition)) >> bitPosition;
}


void setBit(unsigned char *byte, unsigned int bitPosition, unsigned int bitValue)
{
    *byte = (*byte | (1 << bitPosition)) ^ ((bitValue ^ 1) << bitPosition);
}

Can this be improved? The processing speed of the program mainly depends on the speed of these two functions.

UPDATE
I will do a benchmark for each provided answer bellow and write the timings I get. For the reference, the compiler used is gcc on Mac OS X platform:

Apple LLVM version 5.1 (clang-503.0.40) (based on LLVM 3.4svn)

I compile without any specific arguments like: gcc -o program program.c
If you think I should set some optimizations, feel free to suggest.

The CPU is:
2,53 GHz Intel Core 2 Duo

While processing 21.5 MB of data with my originally provided functions it takes about:
Time: 13.565221
Time: 13.558416
Time: 13.566042
Time is in seconds (these are three tries).

-- UPDATE 2 --

I've used the -O3 optimization (gcc -O3 -o program program.c) option and now I'm getting these results:
Time: 6.168574
Time: 6.170481
Time: 6.167839

I'll redo the other benchmarks now...

Answer 1

If you want to stick with functions, then for the first one:

unsigned int getBit(unsigned char *byte, unsigned int bitPosition)
  {
  return (*byte >> bitPosition) & 1;
  }

For the second one:

void setBit(unsigned char *byte, unsigned int bitPosition, unsigned int bitValue)
  {
  if(bitValue == 0)
    *byte &= ~(1 << bitPosition);
  else
    *byte |= (1 << bitPosition);
  }

However, I suspect that the function call/return overhead will swamp the actual bit-flipping. A good compiler might inline these function calls anyways, but you may get some improvement by defining these as macros:

#define getBit(b, p) ((*(b) >> (p)) & 1)

#define setBit(b, p, v) (*(b) = ((v) ? (*(b) | (1 << (p))) : (*(b) & (~(1 << (p))))))

@user694733 pointed out that branch prediction might be a problem and could cause a slowdown. As such it might be good to define separate setBit and clearBit functions:

void setBit(unsigned char *byte, unsigned int bitPosition)
  (
  *byte |= (1 << bitPosition);
  }

void clearBit(unsigned char *byte, unsigned int bitPosition)
  (
  *byte &= ~(1 << bitPosition);
  }

And their corresponding macro versions:

#define setBit(b, p) (*(b) |= (1 << (p)))

#define clearBit(b, p) (*(b) &= ~(1 << (p)))

The separate functions/macros would be useful if the calling code hard-codes the value passed for the bitValue argument in the original version.

Share and enjoy.

Answer 2

How about:

bool getBit(unsigned char byte, unsigned int bitPosition)
{
    return (byte & (1 << bitPosition)) != 0;
}

No need to use a shift operator to "physically" shift the masked-out bit into position 0, just use a comparison operator and let the compiler deal with it. This should of course also be made inline if possible.

For the second one, it's complicated by the fact that it's basically "assignBit", i.e. it takes the new value of the indicated bit as a parameter. I'd try using the explicit branch:

unsigned char setBit(unsigned char byte, unsigned int bitPosition, bool value)
{
  const uint8_t mask = 1 << bitPosition;
  if(value)
    return byte | mask;
  return byte & ~mask;
}

Answer 3

Generally, these things are best left to the compiler's optimizer.

But why do you need functions for such trivial tasks? A C programmer should not get shocked when they encounter basic stuff like this:

x |= 1<<n;      // set bit
x &= ~(1<<n);   // clear bit
x ^= 1<<n;      // toggle bit
y = x & (1<<n); // read bit

There is no real reason to hide simple things like these behind functions. You won't make the code more readable, because you can always assume that the reader of your code knows C. It rather seems like pointless wrapper functions to hide away "scary" operators that the programmer isn't familiar with.

That being said, the introduction of the functions may cause a lot of overhead code. To turn your functions back into the core operations shown above, the optimizer would have to be quite good.

---

If you for some reason persists in using the functions, any attempt of manual optimization is going to be questionable practice. The use of inline, register and such keywords are likely superfluous. The compiler with optimizer enabled should be far more capable to make the decision when to inline and when to put things in registers than the programmer.

As usual, it doesn't make sense to manually optimize code, unless you know more about the given CPU than the person who wrote the compiler port for it. Most often this is not the case.

What you can harmlessly do as manual optimization, is to get rid of unsigned char (you shouldn't be using the native C types for this anyhow). Instead use the uint_fast8_t type from stdint.h. Using this type means: "I would like to have an uint8_t, but if the CPU prefers a larger type for alignment/performance reasons, it can use that instead".

---

EDIT

There are different ways to set a bit to either 1 or 0. For maximum readability, you would write this:

uint8_t val = either_1_or_0;
...

if(val == 1)
  byte |= 1<<n;
else
  byte &= ~(1<<n);

This does however include a branch. Let's assume we know that the branch is a known performance bottleneck on the given system, to justify the otherwise questionable practice of manual optimization. We could then set the bit to either 1 or 0 without a branch, in the following manner:

byte = (byte & ~(1<<n)) | (val<<n);

And this is where the code is turning a bit unreadable. Read the above as:

• Take the byte and preserve everything in it, except for the bit we want to set to 1 or 0.
• Clear this bit.
• Then set it to either 1 or 0.

Note that the whole right side sub-expression is pointless if val is zero. So on a "generic system" this code is possibly slower than the readable version. So before writing code like this, we would have to know that our CPU is very good at bit-flipping and not-so-good at branch prediction.

Answer 4

You can benchmark with the following variations and keep the best of all solutions.

inline unsigned int getBit(unsigned char *byte, unsigned int bitPosition)
{
    const unsigned char mask = (unsigned char)(1U << bitPosition);
    return !!(*byte & mask);
}


inline void setBit(unsigned char *byte, unsigned int bitPosition, unsigned int bitValue)
{
    const unsigned char mask = (unsigned char)(1U << bitPosition);
    bitValue ? *byte |= mask : *byte &= ~mask;
}

If your algorithm expects only zero v/s non zero result from getBit, you can remove !! from return. (To return 0 or 1, I found the version of @BobJarvis really clean)

If your algorithm can pass the bit mask to be set or reset to setBit function, you won't need to calculate mask explicitly.

So depending on the code calling these functions, it may be possible to cut on time.