I want a simple C function which will return true if the n-th bit in a byte is set to1
. Otherwise it will return false.
This is a critical function in terms of execution time, so I am thinking of the most optimal way to do that.
Method 1 (Using Left Shift Operator) 1) Left shift given number 1 by k-1 to create a number that has only set bit as k-th bit. temp = 1 << (k-1) 2) If bitwise AND of n and temp is non-zero, then result is SET else result is NOT SET.
Bitwise AND operation is used to check whether a particular bit is on or off.
Set bits in a binary number is represented by 1. Whenever we calculate the binary number of an integer value then it is formed as the combination of 0's and 1's. So, the digit 1 is known as set bit in the terms of the computer.
The following function can do what you need:
int isNthBitSet (unsigned char c, int n) { static unsigned char mask[] = {128, 64, 32, 16, 8, 4, 2, 1}; return ((c & mask[n]) != 0); }
This assumes 8-bit bytes (not a given in C) and the zeroth bit being the highest order one. If those assumption are incorrect, it simply comes down to expanding and/or re-ordering the mask
array.
No error checking is done since you cited speed as the most important consideration. Do not pass in an invalid n
, that'll be undefined behaviour.
At insane optimisation level -O3
, gcc gives us:
isNthBitSet: pushl %ebp movl %esp, %ebp movl 12(%ebp), %eax movzbl 8(%ebp), %edx popl %ebp testb %dl, mask(%eax) setne %al movzbl %al, %eax ret mask: .byte -128, 64, 32, 16, 8, 4, 2, 1
which is pretty small and efficient. And if you make it static and suggest inlining, or force it inline as a macro definition, you can even bypass the cost of a function call.
Just make sure you benchmark any solution you're given, including this one (a). The number one mantra in optimisation is "Measure, don't guess!"
If you want to know how the bitwise operators work, see here. The simplified AND-only version is below.
The AND operation &
will set a bit in the target only if both bits are set in the tewo sources. The relevant table is:
AND | 0 1 ----+---- 0 | 0 0 1 | 0 1
For a given char
value, we use the single-bit bit masks to check if a bit is set. Let's say you have the value 13 and you want to see if the third-from-least-significant bit is set.
Decimal Binary 13 0000 1101 4 0000 0100 (the bitmask for the third-from-least bit). ========= 0000 0100 (the result of the AND operation).
You can see that all the zero bits in the mask result in the equivalent result bits being zero. The single one bit in the mask will basically let the equivalent bit in the value flow through to the result. The result is then zero if the bit we're checking was zero, or non-zero if it was one.
That's where the expression in the return
statement comes from. The values in the mask
lookup table are all the single-bit masks:
Decimal Binary 128 1000 0000 64 0100 0000 32 0010 0000 16 0001 0000 8 0000 1000 4 0000 0100 2 0000 0010 1 0000 0001
(a)I know how good I am, but you don't :-)
Just check the value of (1 << bit) & byte
. If it is nonzero, the bit is set.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With