Bit manipulation

Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a byte. Programming tasks that require bit manipulation include low-level device control, error detection and correction algorithms, encryption algorithms, and optimization. For most other tasks, modern programming languages allow the programmer to work directly with abstractions instead of bits that represent those abstractions.

Source code that does bit manipulation makes use of the bitwise operations: AND, OR, XOR, NOT, and bit shifts.

Bit twiddling

Bit twiddling and bit bashing are often used interchangeably with bit manipulation, but sometimes to exclusively refer to clever or non-obvious ways or uses of bit manipulation, or tedious or challenging low-level device control or data manipulation tasks. As a derogatory term, "bit twiddling" is the process of tweaking a computer program where vast amounts of time and effort produce negligible improvement, leaving the program source code unreadable to all but the original author.

The term "bit twiddling" dates from early computing hardware, where computer operators would make adjustments by tweaking or "twiddling" computer controls. As computer programming languages evolved, programmers adopted the term to mean any handling of data that involved bit-level computation.

Example of bit manipulation

The following code samples, written in the C programming language, both determine the minimum of two integer values (x and y) and assign the result to r.

// The obvious method if (x < y) r = x; else r = y; // A method using bit manipulation r = y + ((x - y) & -(x < y));

In most cases, the programmer would choose the former method. If it was necessary to find the minimum of two integers millions of times per second, the programmer might exploit his knowledge of binary representation of integers and come up with the latter method. Since that method does not use branching, it runs faster on some processors.dubious

Note that character &amp; represents the bitwise operation "AND" in the C programming language.

Common bit manipulation techniques

Bit manipulation often causes problems with beginning computer programmers, particularly with regard to "good programming habits". The usage of low level assembly instructions to manipulate bits is generally frowned upon. Instead the use of high level bit masks is recommended, since it increases portability and is readable for everyone who knows the language.

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 % 8) can be used to calculate the right bit, and the correct byte with index / 8. A faster version, avoiding the use of the expensive modulus operation, is recommended though: use n = (index & 7) to calculate the right bit, and calculate the correct byte with: index >> 3.

See also

* Bit twiddler
* Bit specification
* Flag &mdash; a bit representing a boolean value
* Nibble &mdash; unit of data consisting of 4 bits, or half a byte
* Mask (computing)
* Bit Twiddling Hacks http://graphics.stanford.edu/~seander/bithacks.html
* [http://bits.stephan-brumme.com Bit Manipulation Tricks] with full explanations and source code

References

* cite book
author = Henry S. Warren Jr.
title = Hacker's Delight
publisher = Addison-Wesley
isbn = 0-201-91465-4

* cite web
author = Sean Eron Anderson
title = Bit Twiddling Hacks
url = http://graphics.stanford.edu/~seander/bithacks.html


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Bit flipping — In computing, bit flipping may mean:* Bit manipulation, algorithmic manipulation of binary digits or bits * Bitwise operation NOT , performing logical negation to a single bit, or each of several bits, switching state 0 to 1, and vice versa *… …   Wikipedia

  • Manipulation — Contents 1 As underhand influence 2 In a physical context 3 In technology 4 See also As underhand influence …   Wikipedia

  • Bit twiddler — In computing, bit twiddler may refer to:* A piece of source code that does bit twiddling , which may mean: ** Doing bit manipulation; ** Interacting with computer hardware, especially when using a bit banging technique; ** Reading or writing… …   Wikipedia

  • Bit specification — In computing, bit specification may mean:* Computer hardware or software capabilities or design features expressed in terms of bit counts. Higher bit specification (e.g. 16 bit vs. 8 bit ) usually indicates better performance. Examples: ** Color… …   Wikipedia

  • Manipulation De Bit — La manipulation de bit est l action de manipuler algorithmiquement des bits ou toute forme de données inférieur à un octet. En informatique, la manipulation de bit est utilisée pour le contrôle bas niveau de périphériques, dans les algorithmes de …   Wikipédia en Français

  • Bit blit — ( bitblt , blitting etc.) is a computer graphics operation in which several bitmap patterns are combined into one using a raster operator .OriginsThe name derives from the BitBLT machine instruction for the Xerox Alto computer, standing for Bit… …   Wikipedia

  • Bit-String —   [dt. Bitfolge, Bitreihe, Bitkette], Datentyp zur Manipulation von binären Werten. Eine Bit Folge der Länge x stellt eine Abfolge von x Bits dar, die durch binäre Operatoren bzw. Funktionen abgefragt, gesetzt und verändert werden können. Bei… …   Universal-Lexikon

  • Manipulation de bit — La manipulation de bit est l action de manipuler algorithmiquement des bits ou toute forme de données inférieur à un octet. En informatique, la manipulation de bit est utilisée pour le contrôle bas niveau de périphériques, dans les algorithmes de …   Wikipédia en Français

  • Bit array — A bit array (or bitmap, in some cases) is an array data structure which compactly stores individual bits (boolean values). It implements a simple set data structure storing a subset of {1,2,..., n } and is effective at exploiting bit level… …   Wikipedia

  • GNU Image Manipulation Program — GIMP GIMP 2.6.3 unter Micr …   Deutsch Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.