What Are Bitwise Operators

What are bitwise operators?

Since nobody has broached the subject of why these are useful:

I use bitwise operations a lot when working with flags. For example, if you want to pass a series of flags to an operation (say, File.Open(), with Read mode and Write mode both enabled), you could pass them as a single value. This is accomplished by assigning each possible flag it's own bit in a bitset (byte, short, int, or long). For example:

 Read: 00000001
Write: 00000010

So if you want to pass read AND write, you would pass (READ | WRITE) which then combines the two into

00000011

Which then can be decrypted on the other end like:

if ((flag & Read) != 0) { //...

which checks

00000011 &
00000001

which returns

00000001

which is not 0, so the flag does specify READ.

You can use XOR to toggle various bits. I've used this when using a flag to specify directional inputs (Up, Down, Left, Right). For example, if a sprite is moving horizontally, and I want it to turn around:

     Up: 00000001
Down: 00000010
Left: 00000100
Right: 00001000
Current: 00000100

I simply XOR the current value with (LEFT | RIGHT) which will turn LEFT off and RIGHT on, in this case.

Bit Shifting is useful in several cases.

x << y

is the same as

x * 2y

if you need to quickly multiply by a power of two, but watch out for shifting a 1-bit into the top bit - this makes the number negative unless it's unsigned. It's also useful when dealing with different sizes of data. For example, reading an integer from four bytes:

int val = (A << 24) | (B << 16) | (C << 8) | D;

Assuming that A is the most-significant byte and D the least. It would end up as:

A = 01000000
B = 00000101
C = 00101011
D = 11100011
val = 01000000 00000101 00101011 11100011

Colors are often stored this way (with the most significant byte either ignored or used as Alpha):

A = 255 = 11111111
R = 21 = 00010101
G = 255 = 11111111
B = 0 = 00000000
Color = 11111111 00010101 11111111 00000000

To find the values again, just shift the bits to the right until it's at the bottom, then mask off the remaining higher-order bits:

Int Alpha = Color >> 24
Int Red = Color >> 16 & 0xFF
Int Green = Color >> 8 & 0xFF
Int Blue = Color & 0xFF

0xFF is the same as 11111111. So essentially, for Red, you would be doing this:

Color >> 16 = (filled in 00000000 00000000)11111111 00010101  (removed 11111111 00000000)
00000000 00000000 11111111 00010101 &
00000000 00000000 00000000 11111111 =
00000000 00000000 00000000 00010101 (The original value)

Bitwise operation and usage

Bitwise operators are operators that work on multi-bit values, but conceptually one bit at a time.

  • AND is 1 only if both of its inputs are 1, otherwise it's 0.
  • OR is 1 if one or both of its inputs are 1, otherwise it's 0.
  • XOR is 1 only if exactly one of its inputs are 1, otherwise it's 0.
  • NOT is 1 only if its input is 0, otherwise it's 0.

These can often be best shown as truth tables. Input possibilities are on the top and left, the resultant bit is one of the four (two in the case of NOT since it only has one input) values shown at the intersection of the inputs.

AND | 0 1     OR | 0 1     XOR | 0 1    NOT | 0 1
----+----- ---+---- ----+---- ----+----
0 | 0 0 0 | 0 1 0 | 0 1 | 1 0
1 | 0 1 1 | 1 1 1 | 1 0

One example is if you only want the lower 4 bits of an integer, you AND it with 15 (binary 1111) so:

    201: 1100 1001
AND 15: 0000 1111
------------------
IS 9 0000 1001

The zero bits in 15 in that case effectively act as a filter, forcing the bits in the result to be zero as well.

In addition, >> and << are often included as bitwise operators, and they "shift" a value respectively right and left by a certain number of bits, throwing away bits that roll of the end you're shifting towards, and feeding in zero bits at the other end.

So, for example:

1001 0101 >> 2 gives 0010 0101
1111 1111 << 4 gives 1111 0000

Note that the left shift in Python is unusual in that it's not using a fixed width where bits are discarded - while many languages use a fixed width based on the data type, Python simply expands the width to cater for extra bits. In order to get the discarding behaviour in Python, you can follow a left shift with a bitwise and such as in an 8-bit value shifting left four bits:

bits8 = (bits8 << 4) & 255

With that in mind, another example of bitwise operators is if you have two 4-bit values that you want to pack into an 8-bit one, you can use all three of your operators (left-shift, and and or):

packed_val = ((val1 & 15) << 4) | (val2 & 15)
  • The & 15 operation will make sure that both values only have the lower 4 bits.
  • The << 4 is a 4-bit shift left to move val1 into the top 4 bits of an 8-bit value.
  • The | simply combines these two together.

If val1 is 7 and val2 is 4:

                val1            val2
==== ====
& 15 (and) xxxx-0111 xxxx-0100 & 15
<< 4 (left) 0111-0000 |
| |
+-------+-------+
|
| (or) 0111-0100

What are bitwise operations?

& is bitwise operator whereas && is conditional operator.You are playing with bitwise operator.

The AND operator specifies that both Signals A and B must be charged for the result to be charged. Therefore, AND-ing the bytes 10 and 6 results in 2, as follows:

a = 0000 1010 (10)

b = 0000 0110 (6)
---- ----
r = 0000 0010 (2) // a&b

See here for more examples:

Bitwise and Bit Shift Operators

~       Unary bitwise complement
<< Signed left shift
>> Signed right shift
>>> Unsigned right shift
& Bitwise AND
^ Bitwise exclusive OR
| Bitwise inclusive OR

Real world use cases of bitwise operators

  • Bit fields (flags)
    They're the most efficient way of representing something whose state is defined by several "yes or no" properties. ACLs are a good example; if you have let's say 4 discrete permissions (read, write, execute, change policy), it's better to store this in 1 byte rather than waste 4. These can be mapped to enumeration types in many languages for added convenience.

  • Communication over ports/sockets
    Always involves checksums, parity, stop bits, flow control algorithms, and so on, which usually depend on the logic values of individual bytes as opposed to numeric values, since the medium may only be capable of transmitting one bit at a time.

  • Compression, Encryption
    Both of these are heavily dependent on bitwise algorithms. Look at the deflate algorithm for an example - everything is in bits, not bytes.

  • Finite State Machines
    I'm speaking primarily of the kind embedded in some piece of hardware, although they can be found in software too. These are combinatorial in nature - they might literally be getting "compiled" down to a bunch of logic gates, so they have to be expressed as AND, OR, NOT, etc.

  • Graphics
    There's hardly enough space here to get into every area where these operators are used in graphics programming. XOR (or ^) is particularly interesting here because applying the same input a second time will undo the first. Older GUIs used to rely on this for selection highlighting and other overlays, in order to eliminate the need for costly redraws. They're still useful in slow graphics protocols (i.e. remote desktop).

Those were just the first few examples I came up with - this is hardly an exhaustive list.

What are bits and bitwise operations used for?

You can pack data in a very concise format.

The smallest amount that an x86 computer can adress is a byte - that's 8 bits.

If your application has a 24 yes/no flags (bools), would you store them in 1 byte each? That's 24 bytes of data. If you use bits, then each byte contains 8 of those bools - so you only need 3 bytes for 24 yes/no values:

> 1 Byte per flag:
> 0000 0000 = off
> 0000 0001 = on
> Easy to check: if(b == 0) { /* flag is off */ } else if(b == 1) { /* flag is on */ }

> 1 Bit per flag
> 0011 1101 = Flags 1, 4, 8, 16 and 32 are on, flags 2, 64 and 128 are off
> Packs 8 flags in 1 byte
> Harder to check:
> if( (b & 32) != 0) { /* Flag 32 is on */ }

This is important for network protocols and other systems where every byte really counts.

For general purpose business applications, there is usually no need for the additional complexity, just use 1 byte per flag.

This isn't just used for bools. For example, some applications may want to store two numbers than can go from 0-15 - an example is the Commodore 64 which really needed to conserve RAM wherever possible. One byte can hold two of those numbers:

> Instead of interpreting this as 8 bits (ranging from 1 to 128)
> this is really two 4 bit numbers:
> 1001 0110
> First Number: 1001 = 1 + 8 = 9
> Second Number: 0110 = 2 + 4 = 6
>
> Getting the first number requires a bit shift to move them into position:
> (b >> 4) turns the above number into this:
> 0000 1001 - this can now be simply cast as a byte and returns 9
>
> The second number requires us to "turn off" the first 4 bits
> We use the AND operator for this: b = (b & 15)
> 15 in decimal is 0000 1111 in binary.
>
> 1001 0110 AND
> 0000 1111 =
> 0000 0110
>
> Once again, the result can be interpreted as a byte and results in the number 6

One more really neat trick is to quickly check if a number is even or odd. An odd number always has the lowest significant bit (the 1 Bit) set, while an even numer always as it clear.

So your check for IsEven looks like this:

return (b & 1) == 0; // Bit 1 not set - number is even

(Note: Depending on the language, Compilers MAY decide to optimize stuff, but in a nutshell, that's it)

What is the purpose of the Bitwise & operator

BLE sends data over the air in bytes. This means that values larger than 255 have to be sent as series of bytes. BLE sends those bytes in little endian format. The code in your question is taking an int32 and converting it into a list of 4 bytes in little endian format.

The conversion can be done as in your example although the Dart language does offer libraries to help with this:

https://api.dart.dev/stable/2.16.1/dart-typed_data/dart-typed_data-library.html

Example of how to use this is at:

Convert int32 to bytes List in dart

Are bitwise operations still practical?

Bitwise operations are worth studying because they have many applications. It is not their main use to substitute arithmetic operations. Cryptography, computer graphics, hash functions, compression algorithms, and network protocols are just some examples where bitwise operations are extremely useful.

The lines you quoted from the Wikipedia article just tried to give some clues about the speed of bitwise operations. Unfortunately the article fails to provide some good examples of applications.

When should I use a bitwise operator?

Bitwise | and & and logical || and && are totally different.

Bitwise operators perform operations on the bits of two numbers and return the result. That means it's not a yes or no thing. If they're being used in conditional statements, they're often used as part of logical comparisons. For example:

if ($x & 2 == 2) {
// The 2^1 bit is set in the number $x
}

Logical operators compare two (or more) conditions/expressions and return true or false. You use them most commonly in conditional statements, like if and while. For example:

if ($either_this || $or_this) {
// Either expression was true
}


Related Topics



Leave a reply



Submit