Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
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...
In logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...
operation can be used, following the principle that Y OR 1 = 1 and Y OR 0 = Y. Therefore, to make sure a bit is on, OR can be used with a 1. To leave a bit unchanged, OR is used with a 0.
Example: turning on the 4th bit
10011101 10010101
OR 00001000 00001000
= 10011101 10011101
Masking bits to 0
There is no way to change a bit from on to off using the OR operation. Instead, bitwise AND is used. When a value is ANDed with a 1, the result is simply the original value, as in: Y AND 1 = Y. However, ANDing a value with 0 is guaranteed to return a 0, so it is possible to turn a bit off by ANDing it with 0: Y AND 0 = 0. To leave the other bits alone, ANDing them with a 1 can be done.
Example: Turning off the 4th bit
10011101 10010101
AND 11110111 11110111
= 10010101 10010101
Querying the status of a bit
It is possible to use bitmasks to easily check the state of individual bits regardless of the other bits. To do this, turning off all the other bits using the bitwise AND is done as discussed above and the value is compared with 0. If it is equal to 0, then the bit was off, but if the value is any other value, then the bit was on. What makes this convenient is that it is not necessary to figure out what the value actually is, just that it is not 0.
Example: Querying the status of the 4th bit
10011101 10010101
AND 00001000 00001000
= 00001000 00000000
Toggling bit values
So far the article has covered how to turn bits on and turn bits off, but not both at once. Sometimes it does not really matter what the value is, but it must be made the opposite of what it currently is. This can be achieved using the XOR (exclusive or) operation. XOR returns 1if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
an odd number of bits are 1. Therefore, if two corresponding bits are 1, the result will be a 0, but if only one of them is 1, the result will be 1. Therefore inversion of the values of bits is done by XORing them with a 1. If the original bit was 1, it returns 1 XOR 1 = 0. If the original bit was 0 it returns 0 XOR 1 = 1. Also note that XOR masking is bit-safe, meaning that it will not affect unmasked bits because Y XOR 0 = Y, just like an OR.
In programming languages such as C, bit masks are a useful way to pass a set of named boolean arguments to a function. For example, in the graphics API OpenGL
OpenGL
OpenGL is a standard specification defining a cross-language, cross-platform API for writing applications that produce 2D and 3D computer graphics. The interface consists of over 250 different function calls which can be used to draw complex three-dimensional scenes from simple primitives. OpenGL...
, there is a command, glClear which clears the screen or other buffers. It can clear up to four buffers (the color, depth, accumulation, and stencil buffers), so the API authors could have had it take four arguments. But then a call to it would look like
glClear(1,1,0,0); // This is not how glClear actually works and would make for unstable code.
which is not very descriptive. Instead there are four defined field bits, GL_COLOR_BUFFER_BIT, GL_DEPTH_BUFFER_BIT, GL_ACCUM_BUFFER_BIT, and GL_STENCIL_BUFFER_BIT and glClear is declared as
void glClear(GLbitfield bits);
Then a call to the function looks like this
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
Internally, a function taking a bitfield like this can use binary and to extract the individual bits. For example, an implementation of glClear might look like:
void glClear(GLbitfield bits) {
if (bits & GL_COLOR_BUFFER_BIT) {
// Clear color buffer.
}
if (bits & GL_DEPTH_BUFFER_BIT) {
// Clear depth buffer.
}
if (bits & GL_ACCUM_BUFFER_BIT) {
// Clear accumulation buffer.
}
if (bits & GL_STENCIL_BUFFER_BIT) {
// Clear stencil buffer.
}
}
The advantage to this approach is that function argument overhead is decreased. Since the minimum datum size is one byte, separating the options into separate arguments would be wasting seven bits per argument and would occupy more stack space. Instead, functions typically accept one or more 32-bit integers, with up to 32 option bits in each. While elegant, in the simplest implementation this solution is not type-safe
Type safety
In computer science, type safety is the extent to which a programming language discourages or prevents type errors. A type error is erroneous or undesirable program behaviour caused by a discrepancy between differing data types...
. A GLbitfield is simply defined to be an unsigned int, so the compiler would allow a meaningless call to glClear(42) or even glClear(GL_POINTS). In C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
an alternative would be to create a class to encapsulate the set of arguments that glClear could accept and could be cleanly encapsulated in a library (see the external links for an example).
Inverse Masks
Masks are used with IP addresses in IP ACLs (Access Control Lists) to specify what should be permitted and denied. To configure IP addresses on interfaces, masks start with 255 and have the large values on the left side: for example, IP address 209.165.202.129 with a 255.255.255.224 mask. Masks for IP ACLs are the reverse: for example, mask 0.0.0.255. This is sometimes called an inverse mask or a wildcard mask. When the value of the mask is broken down into binary (0s and 1s), the results determine which address bits are to be considered in processing the traffic. A 0 indicates that the address bits must be considered (exact match); a 1 in the mask is a "don't care". This table further explains the concept.
Mask Example:
network address (traffic that is to be processed)
10.1.1.0
Based on the binary mask, it can be seen that the first three sets (octets
Octet (computing)
An octet is a unit of digital information in computing and telecommunications that consists of eight bits. The term is often used when the term byte might be ambiguous, as there is no standard for the size of the byte.-Overview:...
) must match the given binary network address exactly (00001010.00000001.00000001). The last set of numbers is made of "don't cares" (.11111111). Therefore, all traffic that begins with 10.1.1. matches since the last octet is "don't care". Therefore, with this mask, network addresses 10.1.1.1 through 10.1.1.255 (10.1.1.x) are processed.
Subtract the normal mask from 255.255.255.255 in order to determine the ACL inverse mask. In this example, the inverse mask is determined for network address 172.16.1.0 with a normal mask of 255.255.255.0.
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
, when a given image is intended to be placed over a background, the transparent areas can be specified through a binary mask. This way, for each intended image there are actually two bitmap
Bitmap
In computer graphics, a bitmap or pixmap is a type of memory organization or image file format used to store digital images. The term bitmap comes from the computer programming terminology, meaning just a map of bits, a spatially mapped array of bits. Now, along with pixmap, it commonly refers to...
s: the actual image, in which the unused areas are given a pixel
Pixel
In digital imaging, a pixel, or pel, is a single point in a raster image, or the smallest addressable screen element in a display device; it is the smallest unit of picture that can be represented or controlled....
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...
s set to 0's, and an additional mask, in which the correspondent image areas are given a pixel value of all bits set to 0's and the surrounding areas a value of all bits set to 1's. In the sample at right, black pixels have the all-zero bits and white pixels have the all-one bits.
At run time, to put the image on the screen over the background, the program first masks the screen pixel's bits with the image mask at the desired coordinates using the bitwise AND operation. This preserves the background pixels of the transparent areas while resets with zeros the bits of the pixels which will be obscured by the overlapped image.
Then, the program renders the image pixel's bits by blending them with the background pixel's bits using the bitwise OR
Logical disjunction
In logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...
operation. This way, the image pixels are appropriately placed while keeping the background surrounding pixels preserved. The result is a perfect compound of the image over the background.
This technique is used for painting pointing device cursors, in typical 2-D videogames for characters, bullets and so on (the sprite
Sprite (computer graphics)
In computer graphics, a sprite is a two-dimensional image or animation that is integrated into a larger scene...
Gui or guee is a generic term to refer to grilled dishes in Korean cuisine. These most commonly have meat or fish as their primary ingredient, but may in some cases also comprise grilled vegetables or other vegetarian ingredients. The term derives from the verb, "gupda" in Korean, which literally...
A computer icon is a pictogram displayed on a computer screen and used to navigate a computer system or mobile device. The icon itself is a small picture or symbol serving as a quick, intuitive representation of a software tool, function or a data file accessible on the system. It functions as an...
s, and for video titling and other image mixing applications.
Although related (due to being used for the same purposes), transparent colors and alpha channels are techniques which do not involve the image pixel mixage by binary masking.
In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
often a function is used that has a large domain. To create an index from the output of the function, a modulo can be taken to reduce the size of the domain to match the size of the array; however, it is often faster on many processors to restrict the size of the hash table to powers of two sizes and use a bit mask instead.
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...
An affinity mask is a bit mask indicating what processor a thread or process should be run on by the scheduler of an operating system. Setting the affinity mask for certain processes running under Windows can be useful as there are several system processes that are restricted to the first CPU / Core...
A subnetwork, or subnet, is a logically visible subdivision of an IP network. The practice of dividing a network into subnetworks is called subnetting....
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, data compression, encryption algorithms, and optimization...
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...
.gif)
In computer graphics