Softpanorama

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

Bit Tricks

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)
LEX YACC XPL PL/360 Prolog Bit Tricks Humor Etc

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:

The fundamental source of useful bit tricks is the book: 

There is also useful information in Knuth volume 4:


Top Visited
Switchboard
Latest
Past week
Past month

NEWS CONTENTS

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



Etc

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

Disclaimer:

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.

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