Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

a function to check if the nth bit is set in a byte

Tags:

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.

like image 307
liv2hak Avatar asked Jan 19 '12 03:01

liv2hak


People also ask

How do you know if the nth bit is set?

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.

What operator checks to see if a bit is on?

Bitwise AND operation is used to check whether a particular bit is on or off.

What is mean by bit is set or not?

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.


2 Answers

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 :-)

like image 161
paxdiablo Avatar answered Sep 22 '22 07:09

paxdiablo


Just check the value of (1 << bit) & byte. If it is nonzero, the bit is set.

like image 34
Jon Avatar answered Sep 24 '22 07:09

Jon