Programming Forums - Bitwise Operators...

Programming Forums (http://www.programmingforums.org/forumindex.php)

- C (http://www.programmingforums.org/forum60.html)

- - Bitwise Operators... (http://www.programmingforums.org/showthread.php?t=15712)

Bitwise Operators...

I have read/looked through like 2 books and 1 online guide about "bitwise operators" such as >> and <<... I just can't express the amount of confusion I have towards these operators xD.

Example:

Quote:

The bitwise AND operator & is often used to mask off some set of bits, for example

n = n & 0177;
sets to zero all but the low-order 7 bits of n.

I just don't get it... I mean... What's the low-order part of bits? And this works for all these "bitwise" operators, I just don't get them xD.

So if someone could explain them more in-depth, more importantly how they are used and what the outcome becomes :P, that would be great ^_^.

-- Them being the commands like >>, &, << and |.

Re: Bitwise Operators...

Bitwise operators work on the specific bits of the value you're modifying. For this reason they'll only work on integer types (floating point numbers are fancy magic). Here's a rough explanation of some of them work (using 8 bit values):

Bitwise shift (<<, >>) just shifts the bits one way or another. Examples:
left shift:
5<<2:

5 in binary is 00000101

shifted left twice is 00010100, which in decimal is 20

Right shift is tricky, since (with most C compilers) it depends on signed-ness of the value. Some other languages let you specify which to use (e.g. Java has >>> for logical shift).
signed: -16 >> 2 (aka, arithmetic shift which preserves signed-ness bit)

-16 in binary is 11110000

shifted right two times is 11111100, which in decimal is -4

132 >> 4 (arithmetic shift)

132 in binary is 10000100

shifted right 4 times is 11111000, which in decimal is 248

Versus logical:
signed: -16 >>> 2 (note: not C syntax, this wouldn't happen in C for signed values)

-16 in binary is 11110000

shifted right two times is 00111100, which in decimal is 60

unsigned: 132 >> 4 (logical shift)

132 in binary is 10000100

shifted right 4 times is 00001000, which in decimal is 16

The AND operator is pretty simple. It compares each corresponding bit pair and sets the result bit if both bits in the pair are set. This is really useful for setting flags. Examples:
255 & 170 == 170

240 & 31 == 0

  11110000

& 00001111

  ---------

  00000000

here's how to check if a specific bit is set: 63 & (1 << 3)

  00111111

& 00001000

  --------

  00001000 (which would be a true value)

The OR operator sets the bit if one or the other is set:
32 | 64 == 96

  01000000

| 00100000

  ---------

  01100000

129 | 7 == 135

While AND is used to check if a flag is set, OR is can be used to set a flag bit to TRUE (value | 1<<n will set the nth bit from the right).

The XOR operator sets the bit only if exactly one of the compared values has it set:
64 ^ 32 == 96

129 ^ 7 == 134

XOR can be used to toggle a bit, similar to the above ones.

Re: Bitwise Operators...

Thank you so much for having such a long post O_O. Really helped me understand them ^_^.

But I have a few more questions :P.

How/When is this used? like for example 5 << 2 is 20... how would i use that to solve/do anything? O_o.
Do you actually have all those binary numbers memorized? O_O

Re: Bitwise Operators...

Jimbo did an excellent job explaining, so I won't re-hash that, but regarding the >> operator, I believe it determines whether or not to preserve the sign bit based on the data types involved. For example:

int x = -5; // x will have its leftmost bit set, as that is how
            // signed values indicate that the value is negative
unsigned y = (unsigned)x; // now y will have its leftmost bit set
                          // as well, but it does not indicate a
                          // negative value here
x = x >> 2; // leftmost bit of x still is set
y = y >> 2; // leftmost bit of y is no longer set

Another thing that should be obvious from Jimbo's explanation is that shifting is a fast way to do integer multiplication and division by powers of two. Want to divide by four? Shift right two places. Multiply by eight? Shift left by three. This can be useful because shifting is far faster for the CPU than actual multiplication or division.

Re: Bitwise Operators...

It's generally not used to do math, because the fact is the difference in speed is pretty much negligible.

Take, for instance, these two programs:

#include <stdio.h>
 
int main() {
    unsigned i, x;
    for(i=1; i<1000000000; i++) x = i << 1;
    return 0;
}

#include <stdio.h>
 
int main() {
    unsigned i, x;
    for(i=1; i<1000000000; i++) x = i * 2;
    return 0;
}

The behaviour of each program is identical, except the first shifts and the second multiplies. They both do a billion shifts or a billion multiplications in the same amount of time.

This is because they are both constant time operations, and most modern compilers will do optimizations under the hood that make these differences negligible.

The place where bit manipulation becomes most useful is in algorithm design, where it becomes valuable to convert a state or vertex into a distinct value for hashing and traversing.

For example, say we are keeping track of a row of 8 coins, that are either heads or tails.

Coin:  1     2     3     4     5     6     7     8

Face:  Tails Tails Heads Tails Heads Tails Heads Heads

If 1 is heads, and 0 is tails, then this can be easily represented by a number:

00101011

That is the number 43 (32+8+2+1).

So you might be wondering how we actually get the number 43 from an array of heads and tails. It can be done by reading each face, while setting and shifting the appropriate bits with bitwise operators.

#include <stdio.h>
 
int main() {
    char coins[] = {'T', 'T', 'H', 'T', 'H', 'T', 'H', 'H'};
    int i, num;
 
    num = 0;
    for(i=0; i<8; i++) 
        if(coins[i] == 'H') 
            num |= ( 1 << (7-i) );
 
    printf("%d\n", num);
    return 0;
}

Bitwise operators also give us the following operations on our set of coins:

The ^ xor operator to flip a coin.
The | or operator to set a coin to heads.
The & and operator to view a coin's face.
The << left shift operator to remove the left-most coin.
The >> right shift operator to remove the right-most coin.
The ~ not operator to flip all coins.

Now, on the spot, I'm going to try make up a programming problem that would require all of this together... hmmm... okay.

Here goes:

Rob is playing Amy in a game of "Coins". "Coins" is a popular game played with 8 pennies, lined up in a row, initially in the configuration: 



    HTHTHTHT



Players alternate turns making 1 of 4 possible moves:



    1) Remove the left coin and place it as heads on the right.

    2) Remove the right coin and place it as tails on the left.

    3) Flip every coin, then set the right-most coin to heads.

    4) Flip any one coin.



The game ends after the 6th turn (3 complete alternations). The goal of the game for the first player is to get as many heads as possible, and for the second player to get as many tails as possible.



The winner is the player with the most of his/her own type. In the event of a tie, the first player wins by default.



In this problem, Rob always starts first and the game ends after Amy's third turn.



------------------------------------------------------------

Input:

An integer t, followed by a string of 8 characters of either 'H' or 'T'.



Output:

A name, either "Rob" or "Amy", representing who will win, given that each player plays perfectly on the t'th turn with the given configuration.



Note:

In random play, the first player is more likely to win than the second player. But in perfect play, the second player will win if he/she has the perfect strategy.

------------------------------------------------------------



Sample Input #1

1 

HTHTHTHT



Sample Output #1

Amy



Sample Input #2

1

THTHTHTH



Sample Output #2

Rob



Sample Input #3

2

HHHTTHTT



Sample Output #3

Rob



Sample Input #4

5

HHHHHHHH



Sample Output #4

Amy

If you know how to write a recursive function, and want to try this out, it should be a great excercise in the advantage of bitwise operators.

Here's my solution. Note that it uses every available bitwise operator. Also note that without converting the sequence of coins into an integer, we could not use a cache where the coin setup is an index into the array. Convenient!

#include <stdio.h>

#define MAX (1<<8)

#define NIL -1



char cache[MAX][8];



char minimax(int coins, int turn) {

    // Accepts configuration of coins, and current turn.

    // Returns the person who wins (0 for Rob, 1 for Amy).

    

    int i, j;

    int tempcoins, isamy;

    if(cache[coins][turn] != NIL) return cache[coins][turn];

    

    if(turn == 7) {

        // Game over; Calculate winner

        for(i=0, j=0; i<8; i++)

            j += (coins & (1 << i)) != 0;

        return cache[coins][turn] = (j < 4);

    }

    isamy = (turn-1)%2;

    

    // Move #1 - Remove the left coin and place it as heads on the right.

    if(minimax(((coins << 1) & 0xFF) | 1, turn+1) == isamy) 

        return cache[coins][turn] = isamy;



    // Move #2 - Remove the right coin and place it as tails on the left.

    tempcoins = coins >> 1;

    if(tempcoins & (1 << 7)) tempcoins ^= (1 << 7);

    if(minimax(tempcoins, turn+1) == isamy) 

        return cache[coins][turn] = isamy;

    

    // Move #3 - Flip every coin, then set the right-most coin to heads

    if(minimax(~coins & 0xFF | 1, turn+1) == isamy) 

        return cache[coins][turn] = isamy;

        

    // Move #4 - Flip any one coin

    for(i=0; i<8; i++) 

        if(minimax(coins ^ (1 << i), turn+1) == isamy)

            return cache[coins][turn] = isamy;

    

    return cache[coins][turn] = !isamy;

}

    

int main() {

    int i, t, h;

    char coins[10];

    

    scanf("%d %s", &t, coins);

    for(h=0, i=0; i<8; i++) 

        if(coins[i] == 'H') 

            h |= (1 << (7-i));

    

    memset(cache, NIL, sizeof(cache));

    printf("%s\n", minimax(h, t) ? "Amy" : "Rob");



    return 0;

}

So, in conclusion, bitwise operators aren't generally used to do math. They should be used just as they were intended: to manipulate and access individual bits, in order to accomplish something more easily and efficiently. Trying to solve this problem without bitwise operators would be extremely painful (and inefficient)!

Re: Bitwise Operators...

Quote:

Originally Posted by Sane (Post 144420)

It's generally not used to do math, because the fact is the difference in speed is pretty much negligible.

...

The behaviour of each program is identical, except the first shifts and the second multiplies. They both do a billion shifts or a billion multiplications in the same amount of time.

This is because they are both constant time operations, and most modern compilers will do optimizations under the hood that make these differences negligible.

Source? I thought (at least in MIPS, we didn't cover x86 specifics at my school) that multiplication and division are not constant time operations, and required multiple assembly instructions to perform the operation and fetch the results.

Re: Bitwise Operators...

It's relatively constant. For 4 byte integers, it is regarded as constant time, as a result of the CPU's cache and the relative number of cycles required.

From my algorithm's textbook:

Quote:

A practical note: it generally does not make sense to recurse all the way down to 1 bit. For most processors, 16-or 32-bit multiplication is a single operation, so by the time the numbers get into this range they should be handed over to the build-in procedure.

And pertaining to the comment about compiler optimizations, I don't have a source handy, but I do remember reading that most modern compilers will automatically make translations like (%2 to &1==0), along with shifting, etc. And, I also remember DaWei once saying that it's best to leave such low-level optimizations to the job of the compiler. If you're really so worried about a few cycles (even though the first code I posted proves there is no measurable difference in number of cycles), then get out your Assembler.

Re: Bitwise Operators...

Quote:

Originally Posted by Sane (Post 144422)

And, I also remember DaWei once saying that it's best to leave such low-level optimizations to the job of the compiler.

That's certainly the sort of thing DaWei would say .... and, if he said it, he's right.

The relative performance of operations (eg multiply by two vs a bit shift) actually depends on the machine your program will run on (eg the instruction set). The majority of good quality, modern, compilers will pick the operation that works best, depending on optimisation settings (eg compiling for speed, compiling for minimum executable file size, etc).

Unless you're writing your own optimising compiler, you are writing highly critical code in assembler, or you have encountered a compiler bug there is usually no need to worry about such things.

Re: Bitwise Operators...

My job often requires that I take the data created by someone else's program - and extract the parts I need into something we can use.

When extracting useful data from various binary files - I often have to use the AND operator ... A common use of bit-wise math is encoding several flags into a single byte.

Suppose the program needed to store these 8 YES/NO flags:

IsPatient_YN
IsDoctor_YN
IsHealthPlan_YN
HasID_YN
HasPhone_YN
HasFax_YN
IsActive_YN
IsDeleted_YN

This could be stored as a series of single-byte entries - each entry using the single character "Y" or "N".

However, using bit-wise operators - the program could store all 8 of these flags in a single byte...

Dim bitflag as byte
If IsPatient_YN == "Y" Then
   bitflag = bitflag OR 1     ' Which sets the right-most (AKA LSB) bit to 1
End If
If IsActive_YN == "Y" Then
   bitflag = bitflag OR 64   ' Which sets this bit:  x1xx xxxx
End If

Then, on reading the data...

If (bitflag AND 1) == 1 Then
    IsPatient_YN = "Y"
Else
    IsPatient_YN = "N"
End If
 
If (bitflag AND 64) == 64 
  IsActive_YN = "Y"
Else
  IsActive_YN = "N"
End If

So, rather than storing the characters "Y" or "N" using 8 bytes - you can store this same information in a single byte.

(This is a small savings - and in these days with large storage devices - some would argue that the space saved is not worth the extra work. But if you're writing a program that deals with millions of individual records - this can be a significant savings...)

A similar algorithm is (was) used in the original DOS directory entries ... the 'archive-bit' was set on a directory entry in certain circumstances. The other bits in that byte controlled the 'read-only' flag - the 'system-file' flag, etc.

Re: Bitwise Operators...

Hey, I have been reading through all of the replies and thanks much for all the time you have put into this ^_^. I'm still pretty confused, but that is just because I haven't fully read through them yet :P.

2 Quick Questions for now since they are on my mind :P

Is this a correct representation of how bits work? Based on what your all saying, it is generally true... (I mean how you read bits)... Link: http://l3d.cs.colorado.edu/courses/C...96/binary.html
I have read that chars are representated by integers correct? Such as Char 'A' is 65? Well, how does the computer recognize the difference between 65 and A? Just wondering ^_^.
Also... When i read through stuff like source codes and the example listed above that is in code... Even with comments, they are confusing and take a few minutes to understand? Is that normal for someone starting out?