Bit manipulation
From Wikipedia, the free encyclopedia
Bit manipulation is the act of algorithmically manipulating bits or other pieces of data shorter than a word. 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 manipulation, in some cases, can obviate or reduce the need to loop over a data structure and can give many-fold speed ups, as bit manipulations are processed in parallel, but the code can become rather more difficult to write and maintain.
Contents |
[edit] Bit twiddling
Bit twiddling and bit bashing are often used interchangeably with bit manipulation, but sometimes exclusively refer to clever or non-obvious ways or uses of bit manipulation, or tedious or challenging low-level device control 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.
[edit] 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. The relative performance of each approach is processor dependent and data dependent. Some processors have fast bit-operations and heavily penalize branching. Other processors employ a branch predictor or speculative execution to mitigate branching costs (breaking-up the instruction pipeline or invalidating the instruction cache) [1]. The data itself affects the success-rate for branch prediction [2]. Programmers can verify which approach is fastest on a given system and dataset by using profiling techniques.
Note that character & represents the bitwise operation "AND" in the C programming language.
[edit] 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 masking 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.
[edit] See also
- Bit twiddler
- Bit specification
- Flag — a bit representing a boolean value
- Nibble — unit of data consisting of 4 bits, or half a byte
- Mask (computing)
[edit] References
- Henry S. Warren Jr.. Hacker's Delight. Addison-Wesley. ISBN 0-201-91465-4.
- Sean Eron Anderson. "Bit Twiddling Hacks". http://graphics.stanford.edu/~seander/bithacks.html.
[edit] External links
- Bit Manipulation Tricks with full explanations and source code
