In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
In computer science, data is information in a form suitable for use with a computer. Data is often distinguished from programs. A program is a sequence of instructions that detail a task for the computer to perform...
Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...
tasks that require bit manipulation include low-level device control, error detection and correction algorithms, data compression
Data compression
In computer science and information theory, data compression, source coding or bit-rate reduction is the process of encoding information using fewer bits than the original representation would use....
In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
In computer science, program optimization or software optimization is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources...
. For most other tasks, modern programming languages allow the programmer
Programmer
A programmer, computer programmer or coder is someone who writes computer software. The term computer programmer can refer to a specialist in one area of computer programming or to a generalist who writes code for many kinds of software. One who practices or professes a formal approach to...
In computer science, abstraction is the process by which data and programs are defined with a representation similar to its pictorial meaning as rooted in the more complex realm of human life and language with their higher need of summarization and categorization , while hiding away the...
instead of bits that represent those abstractions. Source code
Source code
In computer science, source code is text written using the format and syntax of the programming language that it is being written in. Such a language is specially designed to facilitate the work of computer programmers, who specify the actions to be performed by a computer mostly by writing source...
A bitwise operation operates on one or more bit patterns or binary numerals at the level of their individual bits. This is used directly at the digital hardware level as well as in microcode, machine code and certain kinds of high level languages...
s: 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.
Terminology
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.
The history of computing hardware is the record of the ongoing effort to make computer hardware faster, cheaper, and capable of storing more data....
, 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
Computation
Computation is defined as any type of calculation. Also defined as use of computer technology in Information processing.Computation is a process following a well-defined model understood and expressed in an algorithm, protocol, network topology, etc...
.
Example of bit manipulation
The following two code samples, written in the C++ programming language, both determine if the given unsigned integer x is a power of two
Power of two
In mathematics, a power of two means a number of the form 2n where n is an integer, i.e. the result of exponentiation with as base the number two and as exponent the integer n....
.
// The obvious method
unsigned int x = ...;
bool isPowerOfTwo;
if (x > 0) {
while ((x % 2)
0) {
x = x / 2;
}
isPowerOfTwo = (x
1);
}
else
isPowerOfTwo = false;
// A method using bit manipulation
bool isPowerOfTwo = x && !(x & (x - 1));
To understand the second method, please note, that powers of two have one and only one bit set in its binary representation:
x
0...010...0
x-1
0...001...1
x & (x-1)
0...000...0
If the number is not a power of two, it will have '1' in several places:
x
0...1...010...0
x-1
0...1...001...1
x & (x-1)
0...1...000...0
If inline assembler code is used, then an instruction that counts the number of total 1's or 0's can be used, then a comparison after it. If counting the total 1's, then count must be equal to one for it to be a power of 2 for positive numbers. For example, the x86 instruction POPCNT counts the total number of 1's.
Bit manipulation in the C programming language
C has direct support for bitwise operations that can be used for bit manipulation. In the following examples, n is the index of the bit to be manipulated within the variable bit_fld, which is an unsigned char being used as a bit field
Bit field
A bit field is a common idiom used in computer programming to compactly store multiple logical values as a short series of bits where each of the single bits can be addressed separately. A bit field is most commonly used to represent integral types of known, fixed bit-width. A well-known usage of...
. Bit indexing begins at 0, not 1. Bit 0 is the least significant bit.
Set a bit:
bit_fld |= (1 << n)
Clear a bit:
bit_fld &= ~(1 << n)
Toggle a bit:
bit_fld ^= (1 << n)
Test a bit:
bit_fld & (1 << n)
When using an array of bytes to represent set of bits, i.e., a bit array or bitset, the index of the byte in the array associated with a bit n can be calculated using division:
n / CHAR_BIT
where n is the index of the given bit and CHAR_BIT gives the number of bits in a C char.
The index of the bit within the byte indexed by the above can be calculated via a modulo operation
Modulo operation
In computing, the modulo operation finds the remainder of division of one number by another.Given two positive numbers, and , a modulo n can be thought of as the remainder, on division of a by n...
:
n % CHAR_BIT
(Note: unsigned char is typically used in C to represent a byte and CHAR_BIT is most often 8 on modern processors. % is the C modulo operator.)
In computer programming, flag can refer to one or more bits that are used to store a binary value or code that has an assigned meaning, but can refer to uses of other data types...
In computer science, a mask is data that is used for bitwise operations.Using a mask, multiple bits in a byte, nibble, word can be set either on, off or inverted from on to off in a single bitwise operation.-Masking bits to 1:...
Bit banging is a technique for serial communications using software instead of dedicated hardware. Software directly sets and samples the state of pins on the microcontroller, and is responsible for all parameters of the signal: timing, levels, synchronization, etc...
