Bit manipulation is the act of
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
ically manipulating
bits or other pieces of
data
Data ( , ) are a collection of discrete or continuous values that convey information, describing the quantity, quality, fact, statistics, other basic units of meaning, or simply sequences of symbols that may be further interpreted for ...
shorter than a
word
A word is a basic element of language that carries semantics, meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no consensus among linguist ...
.
Computer programming
Computer programming or coding is the composition of sequences of instructions, called computer program, programs, that computers can follow to perform tasks. It involves designing and implementing algorithms, step-by-step specifications of proc ...
tasks that require bit manipulation include low-level device control,
error detection
In information theory and coding theory with applications in computer science and telecommunications, error detection and correction (EDAC) or error control are techniques that enable reliable delivery of digital data over unreliable communi ...
and
correction algorithms,
data compression
In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compressi ...
,
encryption
In Cryptography law, cryptography, encryption (more specifically, Code, encoding) is the process of transforming information in a way that, ideally, only authorized parties can decode. This process converts the original representation of the inf ...
algorithms, and
optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
. For most other tasks, modern
programming language
A programming language is a system of notation for writing computer programs.
Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...
s allow the
programmer
A programmer, computer programmer or coder is an author of computer source code someone with skill in computer programming.
The professional titles Software development, ''software developer'' and Software engineering, ''software engineer' ...
to work directly with
abstractions
Abstraction is a process where general rules and concepts are derived from the use and classifying of specific examples, literal ( real or concrete) signifiers, first principles, or other methods.
"An abstraction" is the outcome of this process ...
instead of bits that represent those abstractions.
Source code
In computing, source code, or simply code or source, is a plain text computer program written in a programming language. A programmer writes the human readable source code to control the behavior of a computer.
Since a computer, at base, only ...
that does bit manipulation makes use of the
bitwise operation
In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operatio ...
s: AND, OR, XOR, NOT, and possibly other operations analogous to the boolean operators; there are also
bit shifts and operations to count ones and zeros, find high and low one or zero, set, reset and test bits, extract and insert fields, mask and zero fields, gather and scatter bits to and from specified bit positions or fields.
Integer arithmetic operators can also effect bit-operations in conjunction with the other operators.
Bit manipulation, in some cases, can obviate or reduce the need to loop over a data structure and can give manyfold speed-ups, as bit manipulations are processed in parallel.
Terminology
''Bit twiddling'', ''bit fiddling'', ''bit bashing'', and ''bit gymnastics'' 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 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
A computation is any type of arithmetic or non-arithmetic calculation that is well-defined. Common examples of computation are mathematical equation solving and the execution of computer algorithms.
Mechanical or electronic devices (or, hist ...
.
Bitwise operation
A bitwise operation operates on one or more
bit patterns or
binary numerals at the level of their individual
bits. It is a fast, primitive action directly supported by the
central processing unit
A central processing unit (CPU), also called a central processor, main processor, or just processor, is the primary Processor (computing), processor in a given computer. Its electronic circuitry executes Instruction (computing), instructions ...
(CPU), and is used to manipulate values for comparisons and calculations.
On most processors, the majority of bitwise operations are single cycle - substantially faster than division and multiplication and branches. While modern processors usually perform some arithmetic and logical operations just as fast as bitwise operations due to their longer
instruction pipeline
In computer engineering, instruction pipelining is a technique for implementing instruction-level parallelism within a single processor. Pipelining attempts to keep every part of the processor busy with some instruction by dividing incoming Mac ...
s and other
architectural
Architecture is the art and technique of designing and building, as distinguished from the skills associated with construction. It is both the process and the product of sketching, conceiving, planning, designing, and construction, constructi ...
design choices, bitwise operations do commonly use less power because of the reduced use of resources.
Example of bit manipulation
To determine if a number is a power of two, conceptually we may repeatedly do integer divide by two until the number won't divide by 2 evenly; if the only factor left is 1, the original number was a power of 2. Using bit and logical operators, there is a simple expression which will return true (1) or false (0):
bool isPowerOfTwo = (x != 0) && ((x & (x - 1)) 0);
The second half uses the fact that powers of two have one and only one bit set in their binary representation:
x 0...0
10...0
x-1 0...001...1
x & (x-1) 0...000...0
If the number is neither zero nor a power of two, it will have '1' in more than one place:
x 0...
1...0
10...0
x-1 0...
1...001...1
x & (x-1) 0...
1...000...0
If inline
assembly language
In computing, assembly language (alternatively assembler language or symbolic machine code), often referred to simply as assembly and commonly abbreviated as ASM or asm, is any low-level programming language with a very strong correspondence bet ...
code is used, then an instruction (
popcnt) that counts the number of 1's or 0's in the operand might be available; an operand with exactly one '1' bit is a power of 2. However, such an instruction may have greater latency than the bitwise method above.
Bit manipulation operations
Processors typically provide only a subset of the useful bit operators. Programming languages don't directly support most bit operations, so idioms must be used to code them. The 'C' programming language, for example provides only bit-wise AND(&), OR(, ), XOR(^) and NOT(~). Fortran provides AND(.and.), OR (.or.), XOR (.neqv.) and EQV(.eqv.). Algol provides syntactic bitfield extract and insert. When languages provide bit operations that don't directly map to hardware instructions, compilers must synthesize the operation from available operators.
An especially useful bit operation is ''count leading zeros'' used to find the high set bit of a machine word, though it may have different names on various architectures.
[On most Intel chips, it's BSR (bitscan reverse), though newer SoCs also have LZCNT (count leading zeros)] There's no simple programming language idiom, so it must be provided by a compiler intrinsic or system library routine. Without that operator, it is ''very'' expensive (see
Find first set#CLZ) to do any operations with regard to the high bit of a word, due to the asymmetric carry-propagate of arithmetic operations. Fortunately, most cpu architectures have provided that since the middle 1980s. An accompanying operation ''count ones'', also called POPCOUNT, which counts the number of set bits in a machine word, is also usually provided as a hardware operator. Simpler bit operations like bit set, reset, test and toggle are often provided as hardware operators, but are easily simulated if they aren't - for example (SET R0, 1; LSHFT R0, i; OR x, R0) sets bit i in operand x.
Some of the more useful and complex bit operations that must be coded as idioms in the programming language and synthesized by compilers include:
*clear from specified bit position up (leave lower part of word)
*clear from specified bit position down (leave upper part of word)
*mask from low bit down (clear lower word)
*mask from high bit up (clear lower word)
*bitfield extract
*bitfield insert
*bitfield scatter/gather operations which distribute contiguous portions of a bitfield over a machine word, or gather disparate bitfields in the word into a contiguous portion of a bitfield (see recent Intel PEXT/PDEP operators). Used by cryptography and video encoding.
*matrix inversion
Some arithmetic operations can be reduced to simpler operations and bit operations:
* reduce multiply by constant to sequence of shift-add
Multiply by 9 for example, is copy operand, shift up by 3 (multiply by 8), and add to original operand.
* reduce division by constant to sequence of shift-subtract
Masking
A mask is data that is used for
bitwise operation
In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operatio ...
s, particularly in a
bit field
A bit field is a data structure that maps to one or more adjacent bits which have been allocated for specific purposes, so that any single bit or group of bits within the structure can be set or inspected. A bit field is most commonly used to repre ...
.
Using a mask, multiple bits in a
Byte
The byte is a unit of digital information that most commonly consists of eight bits. Historically, the byte was the number of bits used to encode a single character of text in a computer and for this reason it is the smallest addressable un ...
,
nibble
In computing, a nibble, or spelled nybble to match byte, is a unit of information that is an aggregation of four- bits; half of a byte/ octet. The unit is alternatively called nyble, nybl, half-byte or tetrade. In networking or telecommuni ...
,
word
A word is a basic element of language that carries semantics, meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no consensus among linguist ...
(etc.) can be set either on, off or inverted from on to off (or vice versa) in a single bitwise operation. More comprehensive applications of masking, when applied conditionally to operations, are termed
predication.
See also
*
Bit array
A bit array (also known as bitmask, bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level par ...
*
Bit banding
*
Bit banging
Bit banging is a term of art that describes a method of digital data transmission as using general-purpose input/output (GPIO) instead of computer hardware that is intended specifically for data communication. Controlling software is responsi ...
*
Bit field
A bit field is a data structure that maps to one or more adjacent bits which have been allocated for specific purposes, so that any single bit or group of bits within the structure can be set or inspected. A bit field is most commonly used to repre ...
*
Bit manipulation instruction set
Bit manipulation instructions sets (BMI sets) are extensions to the x86 instruction set architecture for microprocessors from Intel and AMD. The purpose of these instruction sets is to improve the speed of bit manipulation. All the instructions ...
— bit manipulation extensions for the
x86
x86 (also known as 80x86 or the 8086 family) is a family of complex instruction set computer (CISC) instruction set architectures initially developed by Intel, based on the 8086 microprocessor and its 8-bit-external-bus variant, the 8088. Th ...
instruction set.
*
BIT predicate
*
Bit specification (disambiguation)
*
Bit twiddler (disambiguation)
* ''
Hacker's Delight
''Hacker's Delight'' is a software algorithm book by Henry S. Warren, Jr. first published in 2002. It presents fast bit-level and low-level arithmetic algorithms for common tasks such as counting bits or improving speed of division by using ...
'' – book on fast bit-level and low-level arithmetic algorithms.
*
Nibble
In computing, a nibble, or spelled nybble to match byte, is a unit of information that is an aggregation of four- bits; half of a byte/ octet. The unit is alternatively called nyble, nybl, half-byte or tetrade. In networking or telecommuni ...
— unit of data consisting of 4 bits, or half a byte
*
Predication (computer architecture)
In computer architecture, predication is a feature that provides an alternative to conditional transfer of control, as implemented by conditional branch machine instructions. Predication works by having conditional (''predicated'') non-branc ...
where bit "masks" are used in
Vector processors
*
Single-event upset
*
SIMD within a register (SWAR)
References
Further reading
*
*
Draft of Fascicle 1a available for download)
External links
*
Bit Manipulation Trickswith full explanations and source code
Intel Intrinsics Guidexchg rax, rax x86_64 riddles and hacks
The Aggregate Magic Algorithmsfrom University of Kentucky
{{DEFAULTSORT:Bit Manipulation
Binary arithmetic
Computer arithmetic