|Home||Switchboard||Unix Administration||Red Hat||TCP/IP Networks||Neoliberalism||Toxic Managers|
May the source be with you, but remember the KISS principle ;-)
Skepticism and critical thinking is not panacea, but can help to understand the world better
|News||Compilers Algorithms||Best books||Recommended Links||University Courses||Papers||FAQs||People|
|Lexical analysis||Recursive Descent Parsing||Parsing||Regular expressions||Code generation||Tree-based code optimization||Peephole optimization||Performance and Benchmarks|
|Decompilation||ACM||Program Analysis and Transformations||Pipes coroutunes and continuations||C compilers||Generative programming methods||Graph Analysis||DSL (domain specific languages)|
Bit manipulation, in some cases, can obviate or reduce the need to loop over a data structure and can give dramatic speed ups, as bits are processed in parallel.
Classic use of bit manipulation is imitation of set operations on small sets (for 64 bit computer max number of members for the set is 64, but several words can be used so it still retains speed advantages up to, say, 1024 set members (sixteen words).
The following examples are written in C, but can be applied to any language supporting bitwise operators.
Set a bit (where
n is the bit number, and 0 is the least significant bit):
unsigned char a |= (1 << n);
Clear a bit:
unsigned char b &= ~(1 << n);
Toggle a bit:
unsigned char c ^= (1 << n);
Test a bit:
unsigned char e = d & (1 << n); //d has the byte value.
When manipulating a bitmap consisting of multiple bytes
n = (index % CHAR_BIT) can be used to calculate the right bit,
and the correct byte with
index / CHAR_BIT.
For comprehensive collection of bit tricks see Bit Twiddling Hacks:
There is also useful information in Knuth volume 4:
These macros will be useful if you need to store a lot of yes/no info, in what is known as a bitfield. A bitfield is nothing more than a regual int, except that you manipulate each individual bit, storing either a 1 or a 0 in each.
unsigned int flags;
// Set a bit
flags = flags | 1<<bitindex;
// Clear a bit
flags = flags & ~(1<<bitindex);
// Flip a bit
flags = flags ^ 1<<bitindex;
// Test a bit
if (flags & 1<<bitindex)
printf("Bit %d is set!\n", bitindex);
The Last but not Least Technology is dominated by two types of people: those who understand what they do not manage and those who manage what they do not understand ~Archibald Putt. Ph.D
Copyright © 1996-2018 by Dr. Nikolai Bezroukov. www.softpanorama.org was initially created as a service to the (now defunct) UN Sustainable Development Networking Programme (SDNP) in the author free time and without any remuneration. This document is an industrial compilation designed and created exclusively for educational use and is distributed under the Softpanorama Content License. Original materials copyright belong to respective owners. Quotes are made for educational purposes only in compliance with the fair use doctrine.
FAIR USE NOTICE This site contains copyrighted material the use of which has not always been specifically authorized by the copyright owner. We are making such material available to advance understanding of computer science, IT technology, economic, scientific, and social issues. We believe this constitutes a 'fair use' of any such copyrighted material as provided by section 107 of the US Copyright Law according to which such material can be distributed without profit exclusively for research and educational purposes.
This is a Spartan WHYFF (We Help You For Free) site written by people for whom English is not a native language. Grammar and spelling errors should be expected. The site contain some broken links as it develops like a living tree...
|You can use PayPal to make a contribution, supporting development of this site and speed up access. In case softpanorama.org is down you can use the at softpanorama.info|
The statements, views and opinions presented on this web page are those of the author (or referenced source) and are not endorsed by, nor do they necessarily reflect, the opinions of the author present and former employers, SDNP or any other organization the author may be associated with. We do not warrant the correctness of the information provided or its fitness for any purpose.
Last modified: March 12, 2019