c++ range - How do you set, clear, and toggle a single bit?




geeksforgeeks all (22)

As this is tagged "embedded" I'll assume you're using a microcontroller. All of the above suggestions are valid & work (read-modify-write, unions, structs, etc.).

However, during a bout of oscilloscope-based debugging I was amazed to find that these methods have a considerable overhead in CPU cycles compared to writing a value directly to the micro's PORTnSET / PORTnCLEAR registers which makes a real difference where there are tight loops / high-frequency ISR's toggling pins.

For those unfamiliar: In my example, the micro has a general pin-state register PORTn which reflects the output pins, so doing PORTn |= BIT_TO_SET results in a read-modify-write to that register. However, the PORTnSET / PORTnCLEAR registers take a '1' to mean "please make this bit 1" (SET) or "please make this bit zero" (CLEAR) and a '0' to mean "leave the pin alone". so, you end up with two port addresses depending whether you're setting or clearing the bit (not always convenient) but a much faster reaction and smaller assembled code.

How do you set, clear, and toggle a bit in C/C++?


More general, for arbitrary sized bitmaps:

#define BITS 8
#define BIT_SET(  p, n) (p[(n)/BITS] |=  (0x80>>((n)%BITS)))
#define BIT_CLEAR(p, n) (p[(n)/BITS] &= ~(0x80>>((n)%BITS)))
#define BIT_ISSET(p, n) (p[(n)/BITS] &   (0x80>>((n)%BITS)))

Use the bitwise operators: & |

To set last bit in 000b:

foo = foo | 001b

To check last bit in foo:

if ( foo & 001b ) ....

To clear last bit in foo:

foo = foo & 110b

I used XXXb for clarity. You'll probably be working with HEX representation, depending on the data structure in which you're packing bits.


A C++11 templated version (put in a header):

namespace bit {
    template <typename T1, typename T2> inline void set  (T1 &variable, T2 bit) {variable |=  ((T1)1 << bit);}
    template <typename T1, typename T2> inline void clear(T1 &variable, T2 bit) {variable &= ~((T1)1 << bit);}
    template <typename T1, typename T2> inline void flip (T1 &variable, T2 bit) {variable ^=  ((T1)1 << bit);}
    template <typename T1, typename T2> inline bool test (T1 &variable, T2 bit) {return variable & ((T1)1 << bit);}
}

namespace bitmask {
    template <typename T1, typename T2> inline void set  (T1 &variable, T2 bits) {variable |= bits;}
    template <typename T1, typename T2> inline void clear(T1 &variable, T2 bits) {variable &= ~bits;}
    template <typename T1, typename T2> inline void flip (T1 &variable, T2 bits) {variable ^= bits;}
    template <typename T1, typename T2> inline bool test_all(T1 &variable, T2 bits) {return ((variable & bits) == bits);}
    template <typename T1, typename T2> inline bool test_any(T1 &variable, T2 bits) {return variable & bits;}
}

It is sometimes worth using an enum to name the bits:

enum ThingFlags = {
  ThingMask  = 0x0000,
  ThingFlag0 = 1 << 0,
  ThingFlag1 = 1 << 1,
  ThingError = 1 << 8,
}

Then use the names later on. I.e. write

thingstate |= ThingFlag1;
thingstate &= ~ThingFlag0;
if (thing & ThingError) {...}

to set, clear and test. This way you hide the magic numbers from the rest of your code.

Other than that I endorse Jeremy's solution.


Here's my favorite bit arithmetic macro, which works for any type of unsigned integer array from unsigned char up to size_t (which is the biggest type that should be efficient to work with):

#define BITOP(a,b,op) \
 ((a)[(size_t)(b)/(8*sizeof *(a))] op ((size_t)1<<((size_t)(b)%(8*sizeof *(a)))))

To set a bit:

BITOP(array, bit, |=);

To clear a bit:

BITOP(array, bit, &=~);

To toggle a bit:

BITOP(array, bit, ^=);

To test a bit:

if (BITOP(array, bit, &)) ...

etc.


If you're doing a lot of bit twiddling you might want to use masks which will make the whole thing quicker. The following functions are very fast and are still flexible (they allow bit twiddling in bit maps of any size).

const unsigned char TQuickByteMask[8] =
{
   0x01, 0x02, 0x04, 0x08,
   0x10, 0x20, 0x40, 0x80,
};


/** Set bit in any sized bit mask.
 *
 * @return    none
 *
 * @param     bit    - Bit number.
 * @param     bitmap - Pointer to bitmap.
 */
void TSetBit( short bit, unsigned char *bitmap)
{
    short n, x;

    x = bit / 8;        // Index to byte.
    n = bit % 8;        // Specific bit in byte.

    bitmap[x] |= TQuickByteMask[n];        // Set bit.
}


/** Reset bit in any sized mask.
 *
 * @return  None
 *
 * @param   bit    - Bit number.
 * @param   bitmap - Pointer to bitmap.
 */
void TResetBit( short bit, unsigned char *bitmap)
{
    short n, x;

    x = bit / 8;        // Index to byte.
    n = bit % 8;        // Specific bit in byte.

    bitmap[x] &= (~TQuickByteMask[n]);    // Reset bit.
}


/** Toggle bit in any sized bit mask.
 *
 * @return   none
 *
 * @param   bit    - Bit number.
 * @param   bitmap - Pointer to bitmap.
 */
void TToggleBit( short bit, unsigned char *bitmap)
{
    short n, x;

    x = bit / 8;        // Index to byte.
    n = bit % 8;        // Specific bit in byte.

    bitmap[x] ^= TQuickByteMask[n];        // Toggle bit.
}


/** Checks specified bit.
 *
 * @return  1 if bit set else 0.
 *
 * @param   bit    - Bit number.
 * @param   bitmap - Pointer to bitmap.
 */
short TIsBitSet( short bit, const unsigned char *bitmap)
{
    short n, x;

    x = bit / 8;    // Index to byte.
    n = bit % 8;    // Specific bit in byte.

    // Test bit (logigal AND).
    if (bitmap[x] & TQuickByteMask[n])
        return 1;

    return 0;
}


/** Checks specified bit.
 *
 * @return  1 if bit reset else 0.
 *
 * @param   bit    - Bit number.
 * @param   bitmap - Pointer to bitmap.
 */
short TIsBitReset( short bit, const unsigned char *bitmap)
{
    return TIsBitSet(bit, bitmap) ^ 1;
}


/** Count number of bits set in a bitmap.
 *
 * @return   Number of bits set.
 *
 * @param    bitmap - Pointer to bitmap.
 * @param    size   - Bitmap size (in bits).
 *
 * @note    Not very efficient in terms of execution speed. If you are doing
 *        some computationally intense stuff you may need a more complex
 *        implementation which would be faster (especially for big bitmaps).
 *        See (http://graphics.stanford.edu/~seander/bithacks.html).
 */
int TCountBits( const unsigned char *bitmap, int size)
{
    int i, count = 0;

    for (i=0; i<size; i++)
        if (TIsBitSet(i, bitmap))
            count++;

    return count;
}

Note, to set bit 'n' in a 16 bit integer you do the following:

TSetBit( n, &my_int);

It's up to you to ensure that the bit number is within the range of the bit map that you pass. Note that for little endian processors that bytes, words, dwords, qwords, etc., map correctly to each other in memory (main reason that little endian processors are 'better' than big-endian processors, ah, I feel a flame war coming on...).


Variable used

int value, pos;

value - Data
pos - position of the bit that we're interested to set, clear or toggle
Set a bit

value = value | 1 << pos;

Clear a bit

value = value & ~(1 << pos); 

Toggle a bit

value = value ^ 1 << pos;

I use macros defined in a header file to handle bit set and clear:

/* a=target variable, b=bit number to act upon 0-n */
#define BIT_SET(a,b) ((a) |= (1ULL<<(b)))
#define BIT_CLEAR(a,b) ((a) &= ~(1ULL<<(b)))
#define BIT_FLIP(a,b) ((a) ^= (1ULL<<(b)))
#define BIT_CHECK(a,b) (!!((a) & (1ULL<<(b))))        // '!!' to make sure this returns 0 or 1

/* x=target variable, y=mask */
#define BITMASK_SET(x,y) ((x) |= (y))
#define BITMASK_CLEAR(x,y) ((x) &= (~(y)))
#define BITMASK_FLIP(x,y) ((x) ^= (y))
#define BITMASK_CHECK_ALL(x,y) (((x) & (y)) == (y))   // warning: evaluates y twice
#define BITMASK_CHECK_ANY(x,y) ((x) & (y))

How do you set, clear, and toggle a single bit?

To address a common coding pitfall when attempting to form the mask:
1 is not always wide enough

What problems happen when number is a wider type than 1?
x may be too great for the shift 1 << x leading to undefined behavior (UB). Even if x is not too great, ~ may not flip enough most-significant-bits.

// assume 32 bit int/unsigned
unsigned long long number = foo();

unsigned x = 40; 
number |= (1 << x);  // UB
number ^= (1 << x);  // UB
number &= ~(1 << x); // UB

x = 10;
number &= ~(1 << x); // Wrong mask, not wide enough

To insure 1 is wide enough:

Code could use 1ull or pedantically (uintmax_t)1 and let the compiler optimize.

number |= (1ull << x);
number |= ((uintmax_t)1 << x);

Or cast - which makes for coding/review/maintenance issues keeping the cast correct and up-to-date.

number |= (type_of_number)1 << x;

Or gently promote the 1 by forcing a math operation that is as least as wide as the type of number.

number |= (number*0 + 1) << x;

As with most bit manipulations, best to work with unsigned types rather than signed ones


Setting a bit

Use the bitwise OR operator (|) to set a bit.

number |= 1UL << n;

That will set the nth bit of number. n should be zero, if you want to set the 1st bit and so on upto n-1, if you want to set the nth bit.

Use 1ULL if number is wider than unsigned long; promotion of 1UL << n doesn't happen until after evaluating 1UL << n where it's undefined behaviour to shift by more than the width of a long. The same applies to all the rest of the examples.

Clearing a bit

Use the bitwise AND operator (&) to clear a bit.

number &= ~(1UL << n);

That will clear the nth bit of number. You must invert the bit string with the bitwise NOT operator (~), then AND it.

Toggling a bit

The XOR operator (^) can be used to toggle a bit.

number ^= 1UL << n;

That will toggle the nth bit of number.

Checking a bit

You didn't ask for this, but I might as well add it.

To check a bit, shift the number n to the right, then bitwise AND it:

bit = (number >> n) & 1U;

That will put the value of the nth bit of number into the variable bit.

Changing the nth bit to x

Setting the nth bit to either 1 or 0 can be achieved with the following on a 2's complement C++ implementation:

number ^= (-x ^ number) & (1UL << n);

Bit n will be set if x is 1, and cleared if x is 0. If x has some other value, you get garbage. x = !!x will booleanize it to 0 or 1.

To make this independent of 2's complement negation behaviour (where -1 has all bits set, unlike on a 1's complement or sign/magnitude C++ implementation), use unsigned negation.

number ^= (-(unsigned long)x ^ number) & (1UL << n);

or

unsigned long newbit = !!x;    // Also booleanize to force 0 or 1
number ^= (-newbit ^ number) & (1UL << n);

It's generally a good idea to use unsigned types for portable bit manipulation.

It's also generally a good idea to not to copy/paste code in general and so many people use preprocessor macros (like the community wiki answer further down) or some sort of encapsulation.


Use this:

int ToggleNthBit ( unsigned char n, int num )
{
    if(num & (1 << n))
        num &= ~(1 << n);
    else
        num |= (1 << n);

    return num;
}

From snip-c.zip's bitops.h:

/*
**  Bit set, clear, and test operations
**
**  public domain snippet by Bob Stout
*/

typedef enum {ERROR = -1, FALSE, TRUE} LOGICAL;

#define BOOL(x) (!(!(x)))

#define BitSet(arg,posn) ((arg) | (1L << (posn)))
#define BitClr(arg,posn) ((arg) & ~(1L << (posn)))
#define BitTst(arg,posn) BOOL((arg) & (1L << (posn)))
#define BitFlp(arg,posn) ((arg) ^ (1L << (posn)))

OK, let's analyze things...

The common expression that you seem to be having problems with in all of these is "(1L << (posn))". All this does is create a mask with a single bit on and which will work with any integer type. The "posn" argument specifies the position where you want the bit. If posn==0, then this expression will evaluate to:

    0000 0000 0000 0000 0000 0000 0000 0001 binary.

If posn==8, it will evaluate to

    0000 0000 0000 0000 0000 0001 0000 0000 binary.

In other words, it simply creates a field of 0's with a 1 at the specified position. The only tricky part is in the BitClr() macro where we need to set a single 0 bit in a field of 1's. This is accomplished by using the 1's complement of the same expression as denoted by the tilde (~) operator.

Once the mask is created it's applied to the argument just as you suggest, by use of the bitwise and (&), or (|), and xor (^) operators. Since the mask is of type long, the macros will work just as well on char's, short's, int's, or long's.

The bottom line is that this is a general solution to an entire class of problems. It is, of course, possible and even appropriate to rewrite the equivalent of any of these macros with explicit mask values every time you need one, but why do it? Remember, the macro substitution occurs in the preprocessor and so the generated code will reflect the fact that the values are considered constant by the compiler - i.e. it's just as efficient to use the generalized macros as to "reinvent the wheel" every time you need to do bit manipulation.

Unconvinced? Here's some test code - I used Watcom C with full optimization and without using _cdecl so the resulting disassembly would be as clean as possible:

----[ TEST.C ]----------------------------------------------------------------

#define BOOL(x) (!(!(x)))

#define BitSet(arg,posn) ((arg) | (1L << (posn)))
#define BitClr(arg,posn) ((arg) & ~(1L << (posn)))
#define BitTst(arg,posn) BOOL((arg) & (1L << (posn)))
#define BitFlp(arg,posn) ((arg) ^ (1L << (posn)))

int bitmanip(int word)
{
      word = BitSet(word, 2);
      word = BitSet(word, 7);
      word = BitClr(word, 3);
      word = BitFlp(word, 9);
      return word;
}

----[ TEST.OUT (disassembled) ]-----------------------------------------------

Module: C:\BINK\tst.c
Group: 'DGROUP' CONST,CONST2,_DATA,_BSS

Segment: _TEXT  BYTE   00000008 bytes  
 0000  0c 84             bitmanip_       or      al,84H    ; set bits 2 and 7
 0002  80 f4 02                          xor     ah,02H    ; flip bit 9 of EAX (bit 1 of AH)
 0005  24 f7                             and     al,0f7H
 0007  c3                                ret     

No disassembly errors

----[ finis ]-----------------------------------------------------------------


If you want to perform this all operation with C programming in the Linux kernel then I suggest to use standard APIs of the Linux kernel.

See https://www.kernel.org/doc/htmldocs/kernel-api/ch02s03.html

set_bit  Atomically set a bit in memory
clear_bit  Clears a bit in memory
change_bit  Toggle a bit in memory
test_and_set_bit  Set a bit and return its old value
test_and_clear_bit  Clear a bit and return its old value
test_and_change_bit  Change a bit and return its old value
test_bit  Determine whether a bit is set

Note: Here the whole operation happens in a single step. So these all are guaranteed to be atomic even on SMP computers and are useful to keep coherence across processors.


Check a bit at an arbitrary location in a variable of arbitrary type:

#define bit_test(x, y)  ( ( ((const char*)&(x))[(y)>>3] & 0x80 >> ((y)&0x07)) >> (7-((y)&0x07) ) )

Sample usage:

int main(void)
{
    unsigned char arr[8] = { 0x01, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF };

    for (int ix = 0; ix < 64; ++ix)
        printf("bit %d is %d\n", ix, bit_test(arr, ix));

    return 0;
}

Notes: This is designed to be fast (given its flexibility) and non-branchy. It results in efficient SPARC machine code when compiled Sun Studio 8; I've also tested it using MSVC++ 2008 on amd64. It's possible to make similar macros for setting and clearing bits. The key difference of this solution compared with many others here is that it works for any location in pretty much any type of variable.


int set_nth_bit(int num, int n){

    return (num | 1 << n);
}

int clear_nth_bit(int num, int n){

    return (num & ~( 1 << n));
}

int toggle_nth_bit(int num, int n){

    return num ^ (1 << n);
}

int check_nth_bit(int num, int n){

    return num & (1 << n);
}

Using the Standard C++ Library: std::bitset<N>.

Or the Boost version: boost::dynamic_bitset.

There is no need to roll your own:

#include <bitset>
#include <iostream>

int main()
{
    std::bitset<5> x;

    x[1] = 1;
    x[2] = 0;
    // Note x[0-4]  valid

    std::cout << x << std::endl;
}

[Alpha:] > ./a.out
00010

The Boost version allows a runtime sized bitset compared with a standard library compile-time sized bitset.


Try one of these functions in the C language to change n bit:

char bitfield;

// Start at 0th position

void chang_n_bit(int n, int value)
{
    bitfield = (bitfield | (1 << n)) & (~( (1 << n) ^ (value << n) ));
}

Or

void chang_n_bit(int n, int value)
{
    bitfield = (bitfield | (1 << n)) & ((value << n) | ((~0) ^ (1 << n)));
}

Or

void chang_n_bit(int n, int value)
{
    if(value)
        bitfield |= 1 << n;
    else
        bitfield &= ~0 ^ (1 << n);
}

char get_n_bit(int n)
{
    return (bitfield & (1 << n)) ? 1 : 0;
}

Visual C 2010, and perhaps many other compilers, have direct support for bit operations built in. Surprisingly, this works, even the sizeof() operator works properly.

bool    IsGph[256], IsNotGph[256];

//  Initialize boolean array to detect printable characters
for(i=0; i<sizeof(IsGph); i++)  {
    IsGph[i] = isgraph((unsigned char)i);
}

So, to your question, IsGph[i] =1, or IsGph[i] =0 make setting and clearing bools easy.

To find unprintable characters...

//  Initialize boolean array to detect UN-printable characters, 
//  then call function to toggle required bits true, while initializing a 2nd
//  boolean array as the complement of the 1st.
for(i=0; i<sizeof(IsGph); i++)  {
    if(IsGph[i])    {
         IsNotGph[i] = 0;
    }   else   {
         IsNotGph[i] = 1;
    }
}

Note there is nothing "special" about this code. It treats a bit like an integer - which technically, it is. A 1 bit integer that can hold 2 values, and 2 values only.

I once used this approach to find duplicate loan records, where loan_number was the ISAM key, using the 6-digit loan number as an index into the bit array. Savagely fast, and after 8 months, proved that the mainframe system we were getting the data from was in fact malfunctioning. The simplicity of bit arrays makes confidence in their correctness very high - vs a searching approach for example.


Use one of the operators as defined here.

To set a bit, used int x = x | 0x?; where ? is the bit position in binary form.


This program is to change any data bit from 0 to 1 or 1 to 0:

{
    unsigned int data = 0x000000F0;
    int bitpos = 4;
    int bitvalue = 1;
    unsigned int bit = data;
    bit = (bit>>bitpos)&0x00000001;
    int invbitvalue = 0x00000001&(~bitvalue);
    printf("%x\n",bit);

    if (bitvalue == 0)
    {
        if (bit == 0)
            printf("%x\n", data);
        else
        {
             data = (data^(invbitvalue<<bitpos));
             printf("%x\n", data);
        }
    }
    else
    {
        if (bit == 1)
            printf("elseif %x\n", data);
        else
        {
            data = (data|(bitvalue<<bitpos));
            printf("else %x\n", data);
        }
    }
}

OK, the right answer definitely has to do something with the CPU cache. But to use the cache argument can be quite difficult, especially without data.

There are many answers, that led to a lot of discussion, but let's face it: Cache issues can be very complex and are not one dimensional. They depend heavily on the size of the data, so my question was unfair: It turned out to be at a very interesting point in the cache graph.

@Mysticial's answer convinced a lot of people (including me), probably because it was the only one that seemed to rely on facts, but it was only one "data point" of the truth.

That's why I combined his test (using a continuous vs. separate allocation) and @James' Answer's advice.

The graphs below shows, that most of the answers and especially the majority of comments to the question and answers can be considered completely wrong or true depending on the exact scenario and parameters used.

Note that my initial question was at n = 100.000. This point (by accident) exhibits special behavior:

  1. It possesses the greatest discrepancy between the one and two loop'ed version (almost a factor of three)

  2. It is the only point, where one-loop (namely with continuous allocation) beats the two-loop version. (This made Mysticial's answer possible, at all.)

The result using initialized data:

The result using uninitialized data (this is what Mysticial tested):

And this is a hard-to-explain one: Initialized data, that is allocated once and reused for every following test case of different vector size:

Proposal

Every low-level performance related question on Stack Overflow should be required to provide MFLOPS information for the whole range of cache relevant data sizes! It's a waste of everybody's time to think of answers and especially discuss them with others without this information.







c++ c bit-manipulation bitwise-operators