What USEFUL sequential suppressions of the operator code should a developer know?

Question

I have to say that I never had a reason to use bitwise operators, but I am sure that some of the operations that I performed would be more efficient with them. How did switching and OR-ing help you solve the problem more efficiently?

Answer 1

Check out the famous Beat Twiddling Hacks
Most breeding / dividing is not needed - the compiler will do this automatically, and you will simply confuse people.

But there are many types of "check / set / toggle bit N" that are very useful if you work with hardware or communication protocols.

Answer 2

Using bitwise operations on strings (characters)

Convert lowercase letter:

• OR in space => (x | ' ')
• The result is always lowercase, even if the letter already has lowercase letters
• eg. ('a' | ' ') => 'a' ; ('a' | ' ') => 'a'

Convert letter to uppercase :

• AND by underline => (x & '_')
• The result is always uppercase, even if the letter is already capitalized.
• eg. ('a' & '_') => 'A' ; ('a' & '_') => 'A'

Invert case:

• XOR in space => (x ^ ' ')
• eg. ('a' ^ ' ') => 'A' ; ('a' ^ ' ') => 'A'

Letter position in the alphabet:

• AND chr(31) / binary('11111') / ( hex('1F') => (x & "\x1F")
• The result is in the range 1..26, case is not important
• eg. ('a' & "\x1F") => 1 ; ('B' & "\x1F") => 2

Get the letter position in the alphabet (only for letters Only for the top ):

• AND on ? => (x & '?') or XOR on @ => (x ^ '@')
• eg. ('C' & '?') => 3 ; ('Z' ^ '@') => 26

Get the letter position in the alphabet ( lowercase only):

• XOR using the flyback / chr(96) / binary('1100000') / hex('60') => (x ^ '`')
• eg. ('d' ^ '`') => 4 ; ('x' ^ '`') => 25

Note: using anything other than English letters will produce garbage results

Answer 3

---

• Bitwise Integer Operations (int)

---

Get the maximum integer

 int maxInt = ~(1 << 31); int maxInt = (1 << 31) - 1; int maxInt = (1 << -1) - 1; 

Get the minimum integer

 int minInt = 1 << 31; int minInt = 1 << -1; 

Get maximum length

 long maxLong = ((long)1 << 127) - 1; 

Multiplied by 2

 n << 1; // n*2 

Divided by 2

 n >> 1; // n/2 

Multiplied by the mth power of 2

 n << m; 

Divided by m-th degree 2

 n >> m; 

Check odd number

 (n & 1) == 1; 

Exchange of two values

 a ^= b; b ^= a; a ^= b; 

Get absolute value

 (n ^ (n >> 31)) - (n >> 31); 

Get a maximum of two values

 b & ((ab) >> 31) | a & (~(ab) >> 31); 

Get a minimum of two values

 a & ((ab) >> 31) | b & (~(ab) >> 31); 

Check if both have the same sign

 (x ^ y) >= 0; 

Compute 2 ^ n

 2 << (n-1); 

Is factorial 2

 n > 0 ? (n & (n - 1)) == 0 : false; 

Modulo 2 ^ n vs m

 m & (n - 1); 

Get average

 (x + y) >> 1; ((x ^ y) >> 1) + (x & y); 

Get the mth bit n (low to high)

 (n >> (m-1)) & 1; 

Set the mth bit of n to 0 (low to high)

 n & ~(1 << (m-1)); 

n + 1

 -~n 

n - 1

 ~-n 

Get contrast

 ~n + 1; (n ^ -1) + 1; 

if (x == a) x = b; if (x == b) x = a;

 x = a ^ b ^ x; 

Answer 4

There are only three that I have ever used with any frequency:

• Set bit: a | = 1 <bit;

• Clear bit: a & = ~ (1 <bit);

• Check that the bit is set: a and (1 <bit);

Answer 5

Computational issues: ideas, algorithms, source code, Jörg Arndt (PDF) . This book contains many things, I found it at http://www.hackersdelight.org/

Average value without overflow

Procedure for computing the average (x + y) / 2 of two arguments x and y

 static inline ulong average(ulong x, ulong y) // Return floor( (x+y)/2 ) // Use: x+y == ((x&y)<<1) + (x^y) // that is: sum == carries + sum_without_carries { return (x & y) + ((x ^ y) >> 1); } 

Answer 6

You can compress data, for example. set of integers:

• See which integer values ​​appear more often in the collection.
• Use short bit sequences to represent values ​​that appear more often (and longer bit sequences to represent values ​​that appear less frequently)
• Combining bit sequences: for example, the first 3 bits in the resulting bit stream can represent one integer, then the next 9 bits of another integer, etc.

Answer 7

Counting bit bits, searching for the minimum / highest bit of a set, searching for nth-from-top / bottom bits and others can be useful, and it is worth looking at bit-twiddling hacks .

However, this kind of thing is not everyday. It is useful to have a library, but even then the most common uses are indirect (for example, using a bit container). In addition, ideally, these would be standard library functions - many of them are better handled by specialized CPU instructions on some platforms.

Answer 8

1) Divide / Multiply by Power 2

foo >>= x; (divide by power 2)

foo <<= x; (multiply by power 2)

2) Swap

 x ^= y; y = x ^ y; x ^= y; 

Answer 9

While multiplication / division by shift seems great, the only thing I needed from time to time was to compress Boolean to bits. To do this, you need bitwise AND / OR and possibly bit offset / invert.

Answer 10

I need a function to round numbers to the next maximum power of two, so I visited the Bit Twiddling website, which went up several times and came up with the following:

 i--; i |= i >> 1; i |= i >> 2; i |= i >> 4; i |= i >> 8; i |= i >> 16; i++; 

I use it like size_t . It will probably not reproduce signed types well. If you are worried about portability of platforms with different sizes, cover your code with the #if SIZE_MAX >= (number) directives in the appropriate places.

Answer 11

I used bitwise operators to efficiently perform distance calculations for bit strings . In my application, bitrates were used to represent positions in a sampled space ( octree , if you are interested, encoded using Order Morton ). A distance calculation was necessary to find out if points on the grid were within a certain radius.