Bit Tricks

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:

• About the operation counting methodology
• Compute the sign of an integer
• Detect if two integers have opposite signs
• Compute the integer absolute value (abs) without branching
• Compute the minimum (min) or maximum (max) of two integers without branching
• Determining if an integer is a power of 2
• Sign extending
  • Sign extending from a constant bit-width
  • Sign extending from a variable bit-width
  • Sign extending from a variable bit-width in 3 operations
• Conditionally set or clear bits without branching
• Conditionally negate a value without branching
• Merge bits from two values according to a mask
• Counting bits set
  • Counting bits set, naive way
  • Counting bits set by lookup table
  • Counting bits set, Brian Kernighan's way
  • Counting bits set in 12, 24, or 32-bit words using 64-bit instructions
  • Counting bits set, in parallel
  • Count bits set (rank) from the most-significant bit upto a given position
  • Select the bit position (from the most-significant bit) with the given count (rank)
• Computing parity (1 if an odd number of bits set, 0 otherwise)
  • Compute parity of a word the naive way
  • Compute parity by lookup table
  • Compute parity of a byte using 64-bit multiply and modulus division
  • Compute parity of word with a multiply
  • Compute parity in parallel
• Swapping Values
  • Swapping values with subtraction and addition
  • Swapping values with XOR
  • Swapping individual bits with XOR
• Reversing bit sequences
  • Reverse bits the obvious way
  • Reverse bits in word by lookup table
  • Reverse the bits in a byte with 3 operations (64-bit multiply and modulus division)
  • Reverse the bits in a byte with 4 operations (64-bit multiply, no division)
  • Reverse the bits in a byte with 7 operations (no 64-bit, only 32)
  • Reverse an N-bit quantity in parallel with 5 * lg(N) operations
• Modulus division (aka computing remainders)
  • Computing modulus division by 1 << s without a division operation (obvious)
  • Computing modulus division by (1 << s) - 1 without a division operation
  • Computing modulus division by (1 << s) - 1 in parallel without a division operation
• Finding integer log base 2 of an integer (aka the position of the highest bit set)
  • Find the log base 2 of an integer with the MSB N set in O(N) operations (the obvious way)
  • Find the integer log base 2 of an integer with an 64-bit IEEE float
  • Find the log base 2 of an integer with a lookup table
  • Find the log base 2 of an N-bit integer in O(lg(N)) operations
  • Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup
• Find integer log base 10 of an integer
• Find integer log base 10 of an integer the obvious way
• Find integer log base 2 of a 32-bit IEEE float
• Find integer log base 2 of the pow(2, r)-root of a 32-bit IEEE float (for unsigned integer r)
• Counting consecutive trailing zero bits (or finding bit indices)
  • Count the consecutive zero bits (trailing) on the right linearly
  • Count the consecutive zero bits (trailing) on the right in parallel
  • Count the consecutive zero bits (trailing) on the right by binary search
  • Count the consecutive zero bits (trailing) on the right by casting to a float
  • Count the consecutive zero bits (trailing) on the right with modulus division and lookup
  • Count the consecutive zero bits (trailing) on the right with multiply and lookup
• Round up to the next highest power of 2 by float casting
• Round up to the next highest power of 2
• Interleaving bits (aka computing Morton Numbers)
  • Interleave bits the obvious way
  • Interleave bits by table lookup
  • Interleave bits with 64-bit multiply
  • Interleave bits by Binary Magic Numbers
• Testing for ranges of bytes in a word (and counting occurrences found)
  • Determine if a word has a zero byte
  • Determine if a word has a byte equal to n
  • Determine if a word has byte less than n
  • Determine if a word has a byte greater than n
  • Determine if a word has a byte between m and n
• Compute the lexicographically next bit permutation

Hacker's Delight by Henry Warren: This book contains a collection of programming tricks at the bit level. There is an associated website: www.hackersdelight.org.

There is also useful information in Knuth volume 4:

• Bitwise Tricks and Techniques (A Draft of Section 7.1.3). Latest version is on Don Knuth's website. Here is the version of February 16, 2008: fasc1a_16feb2008.ps.

NEWS CONTENTS

• 190513 : The C Programming Tips and Tricks Wiki - Bit Manipulation ( The C Programming Tips and Tricks Wiki - Bit Manipulation, )

Old News

The C Programming Tips and Tricks Wiki - Bit Manipulation

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

Recommended Links

• Bit manipulation - Wikipedia, the free encyclopedia
• Coranac " Bit tricks
• the bit twiddler
• The Aggregate Magic Algorithms
• Bit Tricks - C And C++ | Dream.In.Code
• String Tricks - A Bit of String Magic (Free Magic Trick)
• Base 2 arithmetic and boolean tricks
• Bit Tricks, Part III- Fast Vertical Counter
• Bit Manipulation
• The Assembly Gems page, tips for the x86 and M680x0, by John Eckerdal
• A Zillion Monkeys, much about programming, particularly about Intel x86 processors, by Paul Hsieh Has a huge list of sites of interest to computer aficionados.
• Programmer's Heaven

Etc

Society

Groupthink : Two Party System as Polyarchy : Corruption of Regulators : Bureaucracies : Understanding Micromanagers and Control Freaks : Toxic Managers :   Harvard Mafia : Diplomatic Communication : Surviving a Bad Performance Review : Insufficient Retirement Funds as Immanent Problem of Neoliberal Regime : PseudoScience : Who Rules America : Neoliberalism  : The Iron Law of Oligarchy : Libertarian Philosophy

Quotes

War and Peace : Skeptical Finance : John Kenneth Galbraith :Talleyrand : Oscar Wilde : Otto Von Bismarck : Keynes : George Carlin : Skeptics : Propaganda  : SE quotes : Language Design and Programming Quotes : Random IT-related quotes :  Somerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose Bierce :  Bernard Shaw : Mark Twain Quotes

Bulletin:

Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks The efficient markets hypothesis : Political Skeptic Bulletin, 2013 : Unemployment Bulletin, 2010 :  Vol 23, No.10 (October, 2011) An observation about corporate security departments : Slightly Skeptical Euromaydan Chronicles, June 2014 : Greenspan legacy bulletin, 2008 : Vol 25, No.10 (October, 2013) Cryptolocker Trojan (Win32/Crilock.A) : Vol 25, No.08 (August, 2013) Cloud providers as intelligence collection hubs : Financial Humor Bulletin, 2010 : Inequality Bulletin, 2009 : Financial Humor Bulletin, 2008 : Copyleft Problems Bulletin, 2004 : Financial Humor Bulletin, 2011 : Energy Bulletin, 2010 : Malware Protection Bulletin, 2010 : Vol 26, No.1 (January, 2013) Object-Oriented Cult : Political Skeptic Bulletin, 2011 : Vol 23, No.11 (November, 2011) Softpanorama classification of sysadmin horror stories : Vol 25, No.05 (May, 2013) Corporate bullshit as a communication method  : Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law

History:

Fifty glorious years (1950-2000): the triumph of the US computer engineering : Donald Knuth : TAoCP and its Influence of Computer Science : Richard Stallman : Linus Torvalds  : Larry Wall  : John K. Ousterhout : CTSS : Multix OS Unix History : Unix shell history : VI editor : History of pipes concept : Solaris : MS DOS :  Programming Languages History : PL/1 : Simula 67 : C : History of GCC development :  Scripting Languages : Perl history   : OS History : Mail : DNS : SSH : CPU Instruction Sets : SPARC systems 1987-2006 : Norton Commander : Norton Utilities : Norton Ghost : Frontpage history : Malware Defense History : GNU Screen : OSS early history

Classic books:

The Peter Principle : Parkinson Law : 1984 : The Mythical Man-Month :  How to Solve It by George Polya : The Art of Computer Programming : The Elements of Programming Style : The Unix Hater’s Handbook : The Jargon file : The True Believer : Programming Pearls : The Good Soldier Svejk : The Power Elite

Most popular humor pages:

Manifest of the Softpanorama IT Slacker Society : Ten Commandments of the IT Slackers Society : Computer Humor Collection : BSD Logo Story : The Cuckoo's Egg : IT Slang : C++ Humor : ARE YOU A BBS ADDICT? : The Perl Purity Test : Object oriented programmers of all nations : Financial Humor : Financial Humor Bulletin, 2008 : Financial Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPL-related Humor : OFM Humor : Politically Incorrect Humor : IDS Humor : "Linux Sucks" Humor : Russian Musical Humor : Best Russian Programmer Humor : Microsoft plans to buy Catholic Church : Richard Stallman Related Humor : Admin Humor : Perl-related Humor : Linus Torvalds Related humor : PseudoScience Related Humor : Networking Humor : Shell Humor : Financial Humor Bulletin, 2011 : Financial Humor Bulletin, 2012 : Financial Humor Bulletin, 2013 : Java Humor : Software Engineering Humor : Sun Solaris Related Humor : Education Humor : IBM Humor : Assembler-related Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor

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

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 Softpanorama society. We do not warrant the correctness of the information provided or its fitness for any purpose. The site uses AdSense so you need to be aware of Google privacy policy. You you do not want to be tracked by Google please disable Javascript for this site. This site is perfectly usable without Javascript.

Last modified: March 12, 2019