Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

practical applications of bitwise operations [closed]

  1. What have you used bitwise operations for?
  2. why are they so handy?
  3. can someone please recommend a VERY simple tutorial?
like image 833
Alex Gordon Avatar asked Oct 07 '10 15:10

Alex Gordon


People also ask

What are the applications of Bitwise Operators?

Examples of uses of bitwise operations include encryption, compression, graphics, communications over ports/sockets, embedded systems programming and finite state machines. A bitwise operator works with the binary representation of a number rather than that number's value.

What is use of Bitwise Operators Explain with examples?

Bitwise operations A bitwise operation operates on two-bit patterns of equal lengths by positionally matching their individual bits. For example, a logical AND (&) of each bit pair results in a 1 if both the first AND second bits are 1. If only one bit is a 1, the result is 0.

What is the significance of using bitwise operator?

Bitwise operators are used to change individual bits in an operand. A single byte of computer memory-when viewed as 8 bits-can signify the true/false status of 8 flags because each bit can be used as a boolean variable that can hold one of two values: true or false.

What is the purpose of bitwise XOR?

The Bitwise Xor operation treats the sign bit as it would any other bit. If one or both inputs for a pixel location are negative, the output is negative; if both inputs are positive, the output is positive.


2 Answers

Although everyone seems to be hooked on the flags usecase, that isn't the only application of bitwise operators (although probably the most common). Also C# is a high enough level language that other techniques will probably be rarely used, but it's still worth knowing them. Here's what I can think of:


The << and >> operators can quickly multiply by a power of 2. Of course, the .NET JIT optimizer will probably do this for you (and any decent compiler of another language as well), but if you're really fretting over every microsecond, you just might write this to be sure.

Another common use for these operators is to stuff two 16-bit integers into one 32-bit integer. Like:

int Result = (shortIntA << 16 ) | shortIntB; 

This is common for direct interfacing with Win32 functions, which sometimes use this trick for legacy reasons.

And, of course, these operators are useful when you want to confuse the inexperienced, like when providing an answer to a homework question. :)

In any real code though you'll be far better off by using multiplication instead, because it's got a much better readability and the JIT optimizes it to shl and shr instructions anyway so there is no performance penalty.


Quite a few curious tricks deal with the ^ operator (XOR). This is actually a very powerful operator, because of the following properties:

  • A^B == B^A
  • A^B^A == B
  • If you know A^B then it's impossible to tell what A and B are, but if you know one of them, you can calculate the other.
  • The operator doesn't suffer from any overflows like multiplication/division/addition/subtraction.

A couple of tricks I have seen using this operator:

Swapping two integer variables without an intermediary variable:

A = A^B // A is now XOR of A and B B = A^B // B is now the original A A = A^B // A is now the original B 

Doubly-linked list with just one extra variable per item. This will have little use in C#, but it might come in handy for low level programming of embedded systems where every byte counts.

The idea is that you keep track of the pointer for the first item; the pointer for the last item; and for every item you keep track of pointer_to_previous ^ pointer_to_next. This way you can traverse the list from either end, yet the overhead is just half that of a traditional linked list. Here's the C++ code for traversing:

ItemStruct *CurrentItem = FirstItem, *PreviousItem=NULL; while (  CurrentItem != NULL ) {     // Work with CurrentItem->Data      ItemStruct *NextItem = CurrentItem->XorPointers ^ PreviousItem;     PreviousItem = CurrentItem;     CurrentItem = NextItem; } 

To traverse from the end you just need to change the very first line from FirstItem to LastItem. That's another memory saving right there.

Another place where I use the ^ operator on a regular basis in C# is when I have to calculate a HashCode for my type which is a composite type. Like:

class Person {     string FirstName;     string LastName;     int Age;      public int override GetHashCode()     {         return (FirstName == null ? 0 : FirstName.GetHashCode()) ^             (LastName == null ? 0 : LastName.GetHashCode()) ^             Age.GetHashCode();     } } 
like image 132
Vilx- Avatar answered Oct 21 '22 20:10

Vilx-


I use bitwise operators for security in my applications. I'll store the different levels inside of an Enum:

[Flags] public enum SecurityLevel {     User = 1, // 0001     SuperUser = 2, // 0010     QuestionAdmin = 4, // 0100     AnswerAdmin = 8 // 1000 } 

And then assign a user their levels:

// Set User Permissions to 1010 // //   0010 // | 1000 //   ---- //   1010 User.Permissions = SecurityLevel.SuperUser | SecurityLevel.AnswerAdmin; 

And then check the permissions in the action being performed:

// Check if the user has the required permission group // //   1010 // & 1000 //   ---- //   1000 if( (User.Permissions & SecurityLevel.AnswerAdmin) == SecurityLevel.AnswerAdmin ) {     // Allowed } 
like image 30
Justin Niessner Avatar answered Oct 21 '22 22:10

Justin Niessner