How do you set, clear, and toggle a single bit?
Solution 1
Setting a bit
Use the bitwise OR operator (|
) to set a bit.
number |= 1UL << n;
That will set the n
th bit of number
. n
should be zero, if you want to set the 1
st bit and so on upto n-1
, if you want to set the n
th 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 n
th 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 n
th 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 n
th bit of number
into the variable bit
.
Changing the nth bit to x
Setting the n
th 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.
or
number = (number & ~(1UL << n)) | (x << n);
(number & ~(1UL << n))
will clear the n
th bit and (x << n)
will set the n
th bit to x
.
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.
Solution 2
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.
Solution 3
The other option is to use bit fields:
struct bits {
unsigned int a:1;
unsigned int b:1;
unsigned int c:1;
};
struct bits mybits;
defines a 3-bit field (actually, it's three 1-bit felds). Bit operations now become a bit (haha) simpler:
To set or clear a bit:
mybits.b = 1;
mybits.c = 0;
To toggle a bit:
mybits.a = !mybits.a;
mybits.b = ~mybits.b;
mybits.c ^= 1; /* all work */
Checking a bit:
if (mybits.c) //if mybits.c is non zero the next line below will execute
This only works with fixed-size bit fields. Otherwise you have to resort to the bit-twiddling techniques described in previous posts.
Solution 4
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
#define BITMASK_SET(x, mask) ((x) |= (mask))
#define BITMASK_CLEAR(x, mask) ((x) &= (~(mask)))
#define BITMASK_FLIP(x, mask) ((x) ^= (mask))
#define BITMASK_CHECK_ALL(x, mask) (!(~(x) & (mask)))
#define BITMASK_CHECK_ANY(x, mask) ((x) & (mask))
Solution 5
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.
JeffV
Electronics Technologist, currently working as a Software Engineer on VR Simulation Systems. Primarily work in Modern C++, C (embedded), Java, C#. Involved in full engineering life cycle including requirements analysis, system decomposition, high level and low level design, implementation and system verification. Designed and implemented sonar processing systems for beam forming line arrays using distributed services and message passing with ZeroMQ. Designed and implemented VR training simulators with hardware stimulation. Designed and implemented wireless blasting receivers for through the earth communications. Extreme low power and reliability design goals: 6mos on a single C-cell battery. Spend my spare time with my wife and daughter, and enjoy mountain biking, boating, scuba, photography and flying. I like to ask the good questions so all can benefit from the answers. Hard to beat the fastest guns in the west around here. ;-)
Updated on July 08, 2022Comments
-
JeffV almost 2 years
How do you set, clear, and toggle a bit?
-
ugasoft over 15 yearsread this: graphics.stanford.edu/~seander/bithacks.html and, when you'll master this, read this one: realtimecollisiondetection.net/blog/?p=78
-
Admin over 15 yearsYou may also be interested in checking out The Bit Twiddler, Bit Twiddling Hacks, and The Aggregate Magic Algorithms.
-
-
Aaron over 15 yearsI would like to note that on platforms that have native support for bit set/clear (ex, AVR microcontrollers), compilers will often translate 'myByte |= (1 << x)' into the native bit set/clear instructions whenever x is a constant, ex: (1 << 5), or const unsigned x = 5.
-
paercebal over 15 years+1. Not that std::bitset is usable from "C", but as the author tagged his/her question with "C++", AFAIK, your answer is the best around here... std::vector<bool> is another way, if one knows its pros and its cons
-
xtofl over 15 yearsNice one, Martin! You can even use an enum to 'index' the bits: enum { cEngineOn, cDoorsOpen, cAircoOn }; std::bitset< cNBBITS > mybits; mybits[ cEngineOn ].set(); const bool cbDoorOpen = mybits[ cDoorsOpen ]; ...
-
moogs over 15 yearsamong the answers here, i think this is the best way to manage bits...but I guess the spirit of the question was how to manipulate bits manually. still, +vote :)
-
Dan over 15 years2 things about this: (1) in perusing your macros, some may incorrectly believe that the macros actually set/clear/flip bits in the arg, however there is no assignment; (2) your test.c is not complete; I suspect if you ran more cases you'd find a problem (reader exercise)
-
andrewdotnich over 15 years@paercebal: vector<bool> isn't very efficient, as bool in C++ takes up a full byte of space, instead of 1 bit…
-
Chris Young over 15 yearsbit = number & (1 << x); will not put the value of bit x into bit unless bit has type _Bool (<stdbool.h>). Otherwise, bit = !!(number & (1 << x)); will..
-
Niklas over 15 years@andrewdotnich: vector<bool> is (unfortunately) a specialization that stores the values as bits. See gotw.ca/publications/mill09.htm for more info...
-
John Zwinck over 15 yearsThese sorts of solutions only work when the target variable is of an integral type. More general solutions can be made to work on other useful target types, such as arrays.
-
R.. GitHub STOP HELPING ICE almost 14 yearsI've always found using bitfields is a bad idea. You have no control over the order in which bits are allocated (from the top or the bottom), which makes it impossible to serialize the value in a stable/portable way except bit-at-a-time. It's also impossible to mix DIY bit arithmetic with bitfields, for example making a mask that tests for several bits at once. You can of course use && and hope the compiler will optimize it correctly...
-
R.. GitHub STOP HELPING ICE almost 14 yearsDon't use a table for a function that can be implemented with a single operator. TQuickByteMask[n] is equivalent to (1<<n). Also, making your arguments short is a very bad idea. The / and % will actually be a division, not bitshift/bitwise and, because signed division by a power of 2 cannot be implemented bitwise. You should make the argument type unsigned int!
-
foraidt almost 14 yearsIt's good to read but one should be aware of possible side effects. Using
BITOP(array, bit++, |=);
in a loop will most likely not do what the caller wants. -
R.. GitHub STOP HELPING ICE almost 14 yearsIndeed. =) One variant you might prefer is to separate it into 2 macros, 1 for addressing the array element and the other for shifting the bit into place, ala
BITCELL(a,b) |= BITMASK(a,b);
(both takea
as an argument to determine the size, but the latter would never evaluatea
since it appears only insizeof
). -
asdf almost 13 yearsWell, it uses inefficient branching.
-
Lundin over 12 years-1 This is just weird obfuscation. Never re-invent the C language by hiding away language syntax behind macros, it is very bad practice. Then some oddities: first, 1L is signed, meaning all bit operations will be performed on a signed type. Everything passed to these macros will return as signed long. Not good. Second, this will work very inefficiently on smaller CPUs as it enforces long when the operations could have been on int level. Third, function-like macros are the root of all evil: you have no type safety whatsoever. Also, the previous comment about no assignment is very valid.
-
Lundin over 12 yearsBit fields are bad in so many ways, I could almost write a book about it. In fact I almost had to do that for a bit field program that needed MISRA-C compliance. MISRA-C enforces all implementation-defined behavior to be documented, so I ended up writing quite an essay about everything that can go wrong in bit fields. Bit order, endianess, padding bits, padding bytes, various other alignment issues, implicit and explicit type conversions to and from a bit field, UB if int isn't used and so on. Instead, use bitwise-operators for less bugs and portable code. Bit fields are completely redundant.
-
Lundin over 12 yearsWhat's the point with this? It only makes the code slower and harder to read? I can't see a single advantage with it. 1u << n is easier to read for C programmers, and can hopefully be translated into a single clock tick CPU instruction. Your division on the other hand, will be translated to something around 10 ticks, or even as bad as up to 100 ticks, depending on how poorly the specific architecture handles division. As for the bitmap feature, it would make more sense to have a lookup table translating each bit index to a byte index, to optimize for speed.
-
Ferruccio over 12 yearsLike most language features, bit fields can be used correctly or they can be abused. If you need to pack several small values into a single int, bit fields can be very useful. On the other hand, if you start making assumptions about how the bit fields map to the actual containing int, you're just asking for trouble.
-
Lundin over 12 yearsAs for big/little endian, big endian will map integers and raw data (for example strings) in the same way: left-to-right msb to lsb throughout the whole bitmap. While little endian will map integers left to right as 7-0, 15-8, 23-18, 31-24, but raw data is still left-to-right msb to lsb. So how little endian is better for your particular algorithm is completely beyond me, it seems to be the opposite.
-
Lundin over 12 yearsMaybe nobody mentioned it because this was tagged embedded. In most embedded systems you avoid STL like the plague. And boost support is likely a very rare bird to spot among most embedded compilers.
-
Lundin over 12 yearsPretty much everything about bit-fields is implementation-defined. Even if you manage to find out all details regarding how your particular compiler implements them, using them in your code will most certainly make it non-portable.
-
Martin York over 12 years@Lundin: Point one not true (some things in the STL are avoided, but a blanket statement like that is just to general, std::bitset is fine and cost nothing to use.). Point two Boost::dynamic_bitset does not depend on anything and can easily be used.
-
Lundin over 12 years@Martin It is very true. Besides specific performance killers like STL and templates, many embedded systems even avoid the whole standard libraries entirely, because they are such a pain to verify. Most of the embedded branch is embracing standards like MISRA, that requires static code analysis tools (any software professionals should be using such tools btw, not just embedded folks). Generally people have better things to do than run static analysis through the whole standard library - if its source code is even available to them on the specific compiler.
-
Martin York over 12 years@Lundin: Your statements are excessively broad (thus useless to argue about). I am sure that I can find situations were they are true. This does not change my initial point. Both of these classes are perfectly fine for use in embedded systems (and I know for a fact that they are used). Your initial point about STL/Boost not being used on embedded systems is also wrong. I am sure there are systems that don't use them and even the systems that do use them they are used judiciously but saying they are not used is just not correct (because there are systems were they are used).
-
Roddy over 12 years@Lundin - True, but embedded system bit-fiddling (particularly in hardware registers, which is what my answer relates to) is never going to be usefully portable anyway.
-
Lundin over 12 yearsNot between entirely different CPUs perhaps. But you most likely want it to be portable between compilers and between different projects. And there is a lot of embedded "bit-fiddling" that isn't related to the hardware at all, such as data protocol encoding/decoding.
-
jeb over 12 years@R.. A table can be useful if your plattform can't shift efficiently, like old microchip mcu's, but of course then the division in the sample is absolutly inefficient
-
endolith over 12 yearsAlternately you could make a
clearbits()
function instead of&= ~
. Why are you using an enum for this? I thought those were for creating a bunch of unique variables with hidden arbitrary value, but you're assigning a definite value to each one. So what's the benefit vs just defining them as variables? -
dmckee --- ex-moderator kitten over 12 years@endolith: The use of
enum
s for sets of related constants goes back a long way in c programing. I suspect that with modern compilers the only advantage overconst short
or whatever is that they are explicitly grouped together. And when you want them for something other than bitmasks you get the automatic numbering. In c++ of course, they also form distinct types which gives you a little extras static error checking. -
endolith about 12 yearsSo the bit order is arbitrary and you can't use this to twiddle individual bits in a microcontroller?
-
Ferruccio about 12 years@endolith: That would not be a good idea. You could make it work, but it wouldn't necessarily be portable to a different processor, or to a different compiler or even to the next release of the same compiler.
-
John U almost 12 yearsMicro was Coldfire MCF52259, using C in Codewarrior. Looking at the disassembler / asm is a useful exercise as it shows all the steps the CPU has to go through to do even the most basic operation. <br>We also spotted other CPU-hogging instructions in time-critical loops - constraining a variable by doing var %= max_val costs a pile of CPU cycles every time round, while doing if(var > max_val)var-=max_val uses only a couple of instructions. <br>A good guide to a few more tricks is here: codeproject.com/Articles/6154/…
-
Igbanam over 11 yearsThis is awesome. My question though is: after checking the
sizeof(mybits)
, I get 12 (i.e. size of threeints
). Is this the space allocated in memory or some bug in thesizeof
function? -
Ferruccio over 11 years@Yasky - what compiler are you using? I get 4 with both VC++11 and Clang 3.1.
-
Igbanam over 11 years@Ferruccio I am using
gcc
version 4.4.5 -
Admin about 11 years...and if you get in the habit of using bit fields doing embedded programming, you'll find your X86 code runs faster, and leaner too. Not in simple benchmarks where you have the whole machine to crush the benchmark, but in real-world multi-tasking environments where programs compete for resources. Advantage CISC - whose original design goal was to make up for CPUs faster than buses and slow memory.
-
Martin York about 11 years@jons34yp: The SGI documentation is more conical and generally has less mistakes than cppreference.
-
Happy Green Kid Naps almost 11 yearsIt's just me, but I'd prefer to parenthesize the bit shift expressions (similar to what @Aaron has done above).
-
anatolyg almost 11 yearsBTW the bit-fiddling here will silently fail if
number
is wider thanint
-
aaronman almost 11 yearswhy don't you change the last one to
bit = (number >> x) & 1
-
phuclv almost 11 years@Aaron: x86 has native bit test and set/clear/complement instructions too
-
mloskot over 10 yearsThe topic clearly states C language, not C++. Clearly, this is incorrect answer, so how on earth it received 120+ upvotes?!
-
Martin York over 10 years@mloskot: The question clearly states C++. Its in the tag below the question what languages are valid. It got 120+ up-votes because people who can read read the question and correctly evaluated in the context of the tags. :-) Ohh. And it is simple.
-
mloskot over 10 years@LokiAstari I dare to claim either the tag is incorrect or the topic and body is impreciese. This is important issue, as it leads to SO questions become vague, thus useless really.
-
Admin over 10 yearsI think there is a problem in the notation. Say I have 0011 (decimal 3) and I want to check if second bit is set, e.g., the one in bold: 0 0 1 1. How do you refer to x? Will it be 2nd or 1st bit according to your notation, because if it is 2nd bit, I think you suggestion won't work, e.g., since you will shift 1 two times, and get 100 - which won't yield 2nd bit as I defined above. Isn't it?
-
Robert Kelly over 10 yearsUh I realize this is a 5 year old post but there is no argument duplication in any of those macros, Dan
-
Siyuan Ren over 10 years
1
is anint
literal, which is signed. So all the operations here operate on signed numbers, which is not well defined by the standards. The standards does not guarantee two's complement or arithmetic shift so it is better to use1U
. -
Shade almost 10 years@R. It is possible to use both, the
struct
can be put inside a (usually anonymous)union
with an integer etc. It works. (I realize this is an old thread btw) -
JonS almost 10 yearsTo clarify anatolyg's comment, the constant "1" with no modifiers is defined to be a signed int. To have this work properly for all variables, use "1ULL" instead.
-
sudo over 9 yearsAll I know is that every single time I try to compile something made in C++, Boost becomes my new worst enemy. Still up-voted anyway.
-
Martin York over 9 years@9000: Why? You should not be doing anything with boost. This is a header only library and installing boost should be package management things
sudo apt-get install boost-devel
-
Luis Colorado over 9 yearsThe question asked for C/C++, so to be compliant with both world I think STL is not applicable here.
-
Luis Colorado over 9 yearsYou'll get into undefined enum constants if you don't define a constant for each of the possible values of the bits. What's the
enum ThingFlags
value forThingError|ThingFlag1
, for example? -
Martin York over 9 years@LuisColorado: Yet not to talk about it would mean not having the information available for users. The point is not limit your answer but to provide a solution. The OP will decide if it is relevant by putting a tick mark by the best answer. You vote up if you think it is an answer that is useful to the community or down if it has no value to the community.
-
Martin York over 9 years@LuisColorado: I disagree. It solved the problem in a way that others had not mentioned. Admittedly it was for a subset of people that used C++ but the question was tagged as C++ and thus a valid answer.
-
Luis Colorado over 9 years@LokiAstari, and that's the reason i just made a comment, no downvote, nothing else... just a comment.
-
galinette over 9 yearsstd::bitset is indeed implemented as bits by most compilers
-
Admin over 9 years@galinette, Agreed. The header file #include <bitset> is a good resource in this regard. Also, the special class vector<bool> for when you need the size of the vector to change. The C++ STL, 2nd Edition, Nicolai M. Josuttis covers them exhaustively on pgs 650 and 281 respectively. C++11 adds a few new capabilities to std::bitset, of special interest to me is a hash function in unordered containers. Thanks for the heads up! I'm going to delete my brain-cramp comment. Already enough garbage out on the web. I don't want to add to it.
-
brigadir over 9 years
BITMASK_CHECK(x,y) ((x) & (y))
must be((x) & (y)) == (y)
otherwise it returns incorrect result on multibit mask (ex.5
vs.3
) /*Hello to all gravediggers :)*/ -
M.M about 9 years@JonS for all variables up to
unsigned long long
in size anyway... there may be implementation-defined extensions such as__int128
. To be ultra-safe(uintmax_t)1 << x
-
M.M about 9 years
1
should be(uintmax_t)1
or similar in case anybody tries to use these macros on along
or larger type -
M.M about 9 yearsThis will fail if
arg
islong long
.1L
needs to be the widest possible type, so(uintmax_t)1
. (You might get away with1ull
) -
M.M about 9 years
CHAR_BIT
is already defined bylimits.h
, you don't need to put in your ownBITS
(and in fact you make your code worse by doing so) -
M.M about 9 years@asdf The compiler's job is to output the most efficient binary, the programmer's job is to write clear code
-
M.M about 9 yearsThis uses at least a whole byte of storage for each
bool
. Maybe even 4 bytes for C89 setups that useint
to implementbool
-
M.M about 9 years
value << n
may cause undefined behaviour -
Admin about 9 years@MattMcNabb, you are correct. In C++ the size of the int type necessary to implement a boolean is not specified by the standard. I realized this answer was in error some time ago, but decided to leave it here as people are apparently finding it useful. For those wanting to use bits galinette's comment is most helpful as is my bit library here ... stackoverflow.com/a/16534995/1899861
-
Ben Voigt about 9 yearsEven more importantly, the helper memory-mapped I/O registers provide a mechanism for atomic updates. Read/modify/write can go very badly if the sequence is interrupted.
-
Ben Voigt about 9 yearsThis is a good demonstration of testing, setting, and clearing a particular bit. However it's a very bad approach for toggling a bit.
-
Ben Voigt about 9 years@RocketRoy: Probably worth changing the sentence that claims this is an example of "bit operations", then.
-
leoly about 9 yearsI prefer
number = number & ~(1 << n) | (x << n);
for Changing the n-th bit to x. -
chqrlie about 9 years@Jiashuo Li: this statement will fail if
number
is larger thanint
andn
is greater or equal to the number of bits in anint
. It even invokes undefined behaviour in this case.number = number & ~((uintmax_t)1 << n) | ((uintmax_t)x << n);
is a generic expression that should work for all sizes ofnumber
but may generate ugly and inefficient code for smaller sizes. -
Anonymous about 9 yearsRelated to checking a bit: Why not simply use "number & 0x01" for checking the first bit, "number & 0x08" for the fourth etc. Imho more beautiful.
-
PC Luddite over 8 years@R.. This answer is really old, but I'd probably prefer a function to a macro in this case.
-
Lundin over 8 yearsIf you use this method please keep in mind that enum constants are always of signed type
int
. This can cause all manner of subtle bugs because of implicit integer promotion or bitwise operations on signed types.thingstate = ThingFlag1 >> 1
will for example invoke implementation-defined behavior.thingstate = (ThingFlag1 >> x) << y
can invoke undefined behavior. And so on. To be safe, always cast to an unsigned type. -
Lundin over 8 years@Shade There are no guarantees that the bit field bits map in a sane, predictable manner to the other data types in the same union. All such code will at best be completely non-portable.
-
Lundin over 8 yearsKeep in mind that all port registers will be defined as
volatile
and therefore the compiler is unable to perform any optimizations on code involving such registers. Therefore, it is good practice to disassemble such code and see how it turned out on assembler level. -
Kevin over 8 yearsUsing operations like
-x
is not safe since the C standard allows signed integers to be (e.g.) sign-magnitude, ones' complement, or any other system that can express the necessary range, meaning that-x
is not required to be the same as(~x) + 1
. This isn't that big of a deal on modern architectures, but you never know what a sufficiently clever optimizing compiler will do with your code. -
Aiken Drum about 8 years@Lundin: As of C++11, you can set the underlying type of an enumeration, e.g.:
enum My16Bits: unsigned short { ... };
-
Kelly S. French over 7 years@Yasky and Ferruccio getting different answers to a sizeof() for this approach should illustrate the problems with compatibility not just across compilers but across hardware. We sometimes fool ourselves that we've solved these issues with languages or defined runtimes but it really comes down to 'will it work on my machine?'. You embedded guys have my respect (and sympathies).
-
71GA over 7 yearsWhy do we use
~
instead!
? -
mckenzm about 7 years@Anonymous. We use masks anyway so that if we ever need to do more than one extension is obvious ? Side note, uppercase/lowercase in EBCDIC is 1 bit.
-
Patrick Roberts almost 7 yearsDoesn't the last example assume twos-complement representation? Isn't that bad / non-portable, whatever you want to call it?
-
Adrian McCarthy over 6 years@71GA: Bitwise negation (
~
) inverts all the bits, so~0xFFF0FFFF
is0x000F0000
. Boolean not (!
) gives 0 if the value is non-zero or 1 if the value is zero, so!0xFFF0FFFF
is0x00000000
. -
chux - Reinstate Monica over 6 yearsMinor: the 3rd
(size_t)
cast seem to be there only to insure some unsigned math with%
. Could(unsigned)
there. -
chux - Reinstate Monica over 6 yearsThe
(size_t)(b)/(8*sizeof *(a))
unnecessarily could narrowb
before the division. Only an issue with very large bit arrays. Still an interesting macro. -
chqrlie over 6 yearsInteresting look on an old question! Neither
number |= (type_of_number)1 << x;
nornumber |= (number*0 + 1) << x;
appropriate to set the sign bit of a signed type... As a matter of fact, neither isnumber |= (1ull << x);
. Is there a portable way to do it by position? -
chux - Reinstate Monica over 6 years@chqrlie IMO, the best way to avoid setting the sign bit and risking UB or IDB with shifts is to use unsigned types. Highly portable shift signed code is too convoluted to be acceptable.
-
Peter Cordes over 6 years@PatrickRoberts: Yes, it does require 2's complement. In one's complement,
-1
is0b1111..1110
. (All-ones is-0
). C++ also allows sign/magnitude integer representations, where-x
just flips the sign bit. I updated this answer to point that out. It's totally fine if you are only targeting 2's complement C++ implementations. It's not UB, it's merely implementation-defined, so it is required to work correctly on implementations the define signed integers as 2's complement. I also changed the constants to1UL
, with a note that1ULL
may be required. -
Peter Cordes over 6 years@Kevin: It is guaranteed to be safe on a C++ implementation that uses 2's complement. It's "implementation defined", not UB. The thing to worry about is portability to one's complement or sign/magnitude, not optimizing compilers.
-
Kevin over 6 years@Peter
-x
is UB if x is INT_MIN. -
Peter Cordes over 6 years@Kevin: oh right, should be
-(unsigned long)x
which would also sidestep the signed-integer representation. (unsigned base 2 matches 2's complement semantics.) But it only works correctly ifx
is 0 or 1. Remember we're setting bitn
tox
. -
Kevin over 6 years@PeterCordes: That's entirely reasonable. But when a developer tells me "this invariant will always hold!" I get real nervous.
-
Peter Cordes over 6 years@Kevin: I decided to leave out any mention of signed-overflow UB in my last edit, because you want to use unsigned anyway for portable
0U - 1U
-> all-ones. How does it look now? I tried to keep the answer simple. I did mention that you may need to booleanize with!!x
. If this was my own answer, I might insert more text about always using unsigned, but I'm just maintaining this old canonical answer. (Jeremy, hope you like the changes, you might want to edit to put my changes into your own words or whatever else you want to say nearly 9 years later.) -
Peter Cordes over 6 yearsJust noticed in the edit history that the changing
n
th bit tox
section was added by another 3rd-party edit, and wasn't Jeremy's work in the first place. -
Peter Cordes over 6 yearsOr
1ULL
works as well as(uintmax_t)
on most implementations. -
Peter Cordes over 6 years@brigadir: depends whether you want to check for any bits set or all bits set. I updated the answer to include both with descriptive names.
-
Peter Cordes over 6 yearsDid you optimize for code-size? On Intel mainstream CPUs you'll get partial-register stalls when reading AX or EAX after this function returns, because it writes the 8-bit components of EAX. (It's fine on AMD CPUs, or others that don't rename partial registers separately from the full register. Haswell/Skylake don't rename AL separately, but they do rename AH.).
-
melpomene about 6 yearsThis code is broken. (Also, why do you have
;
after your function definitions?) -
Joakim L. Christiansen about 6 years@melpomene The code is not broken, I did test it. Do you mean that it will not compile or that the result is wrong? About the extra ';' I don't remember, those can be removed indeed.
-
melpomene about 6 years
(variable & bits == bits)
? -
Joakim L. Christiansen about 6 yearsThank you for noticing, it was supposed to be
((variable & bits) == bits)
-
Handy999 over 5 years
BITMASK_CHECK_ALL(x,y)
can be implemented as!~((~(y))|(x))
-
Tavian Barnes over 4 years@Handy999 It's a bit easier to see why that works after applying De Morgan's law and re-arranging to get
!(~(x) & (y))
-
pqnet over 4 yearsuse
std::bitset
in c++11 -
Chandra Shekhar over 4 yearsThanks for the detailed explanation. Here is the link for practice problem for BIT Magic link
-
Peter - Reinstate Monica over 4 years@MartinYork The embedded world is wide; but if the STL is avoided and instead some containers etc. are self-written the code is almost certainly less performant and contains more bugs. (I was working on one such system in the early 2000s. It was embedded alright, infotainment, but had the resources of a PC 5 years before.)
-
Martin York over 4 years@Peter-ReinstateMonica we are talking explicitly about the
std::bitset
only here. -
Peter - Reinstate Monica over 4 years@MartinYork I was trying to support your statement; " STL/Boost not being used on embedded systems is also wrong" is correct. It is used. (And sometimes, when the system is sufficiently capable and the software is sufficiently complex it is actually a mistake not to use the STL because the alternatives -- no generics, or home-grown -- are worse.)
-
avivgood2 about 4 yearsIs you method of Changing the nth bit to x valid for C90 as well? And is this answered valid for unsigned numbers as well?
-
Asteroids With Wings about 4 yearsUnfortunately you can't even see the code without scrolling sideways, as it's so verbose. Perhaps a few newlines would help?
-
Xeverous almost 4 yearsReturn type of
check_nth_bit
can bebool
. -
Sazzad Hissain Khan almost 4 years@Xeverous yes it depends on callers intention
-
Admin almost 4 yearsyou might want
__attribute__((packed))
-
sherrellbc over 3 yearsI've run into this somewhat infrequently and always had the thought that I should come up with a single expression to do the
set bit to value
operation. Generally I do thesave state
+unconditionally set/clear
+restore state
in hardware. Anyway, I randomly stumbled on this and will definitely steal the expression above. -
Shogan Aversa-Druesne over 3 years
number = (number | (1UL << n)) ^ (!x << n)
Simplified to remove a logical not and a bitwise not -
Shogan Aversa-Druesne over 3 yearsthe above expression ^^^^^ allowing x to be unrestricted, x can be 0 or any positive number for true and is not tied to 0 and 1
-
William Martens about 3 yearsThis was so extremely useful I wonder why I haven't tried this before, especially
#define BIT_CHECK(a,b) (!!((a) & (1ULL<<(b)))) // '!!' to make sure this returns 0 or 1
-
Admin about 3 yearschange
1
to0x1
or1UL
to avoid UB @M.M is talking about -
Smartskaft2 about 3 yearsSometimes I wonder if not a simple if/else-statement would be more efficient when changing the n th bit to
x
. Would notnumber = (number & ~(1UL << n)) | (x << n);
generate two bit shifts, one byte flip, one AND, one OR and lastly one assignment. Whileif (x) { number |= (1 << n); } else { number &= ~(1 << n); }
would generate one "comparison", one bit shift, either an OR or an AND with a byte flip, as well as an assignment. 6 vs 5 operations in the worst case (clearing the bit). 6 vs 4 when setting the bit. Much more readable. But maybe some ops are more costly? -
Angra Mainyu about 3 years@Smartskaft2 the problem is that branching with if/else may be much more expensive. Look up "branch prediction failure", or see this question: stackoverflow.com/q/11227809
-
Will Eccles almost 3 yearsThis could be much more succinctly (and likely more efficiently, unless the compiler optimizes your solution) as
(number & ~(1 << n)) | (!!x << n)
. -
JulianW almost 3 years@AngraMainyu Branch prediction errors are negligibly small: godbolt.org/z/vascq9Khc the if solution is even 1.2 times faster.
-
Angra Mainyu almost 3 years@JulianH Thanks for testing. But in that test we have a fixed pattern of alternating true/false in the branch condition, which the branch predictor will likely predict perfectly after the first few iterations. So the test does not actually measure branch prediction failure.
-
JulianW almost 3 years@AngraMainyu The CPU does not predict perfectly as you said, since there is a speedup difference between alternating and non alternating
x
, however, when randomizing the x's value, the non-if
-solution is aobut twice as fast as theif
-solution: godbolt.org/z/5aEbKchzf So, yeah you are right, branch prediction kills the performance. -
Peter Mortensen over 2 yearsThis answer is featured in Joel Spolsky's 2009 Google Tech Talk, at 17 min 10 secs.
-
Miral over 2 yearsThe best way to check a bit is
(number & (1UL << n)) != 0
(or use!!
if you prefer) since this produces a boolean result rather than an integer (and this is usually done in boolean contexts such as if statements). While an integer expression is legal and will behave correctly in boolean contexts, depending on compiler settings it may produce a warning. Note that you need a slightly different expression to check a bitmask of multiple bits, depending on whether you're wanting to check for any bits or all bits. -
Koby 27 over 2 yearsThe improvement suggested by @leoly is a must. I didn't see this commented, but the toggling, messes the other bits of the number as far as I can tell. Correct me If I'm wrong.