Programming Forums > Application Development > C

redfiretruck · Apr 26th, 2008, 7:33 PM

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

, that would be great ^_^.

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

Jimbo · Apr 26th, 2008, 8:21 PM

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:

(Toggle Plain Text)

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)

(Toggle Plain Text)

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

132 >> 4 (arithmetic shift)

(Toggle Plain Text)

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)

(Toggle Plain Text)

-16 in binary is 11110000
shifted right two times is 00111100, which in decimal is 60

unsigned: 132 >> 4 (logical shift)

(Toggle Plain Text)

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

(Toggle Plain Text)

  11111111
& 10101010
  --------
  10101010

240 & 31 == 0

(Toggle Plain Text)

  11110000
& 00001111
  ---------
  00000000

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

(Toggle Plain Text)

  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

(Toggle Plain Text)

  01000000
| 00100000
  ---------
  01100000

129 | 7 == 135

(Toggle Plain Text)

  10000001
| 00000111
  --------
  10000111

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

(Toggle Plain Text)

  01000000
^ 00100000
  --------
  01100000

129 ^ 7 == 134

(Toggle Plain Text)

  10000001
^ 00000111
  --------
  10000110

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

redfiretruck · Apr 26th, 2008, 11:52 PM

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

But I have a few more questions

.

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

lectricpharaoh · Apr 27th, 2008, 12:12 AM

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:

 C Syntax (Toggle Plain Text) 
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
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.

Sane · Apr 27th, 2008, 2:20 PM

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:

 C Syntax (Toggle Plain Text) 
#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 << 1;
    return 0;
}

 C Syntax (Toggle Plain Text) 
#include <stdio.h>
 
int main() {
    unsigned i, x;
    for(i=1; i<1000000000; i++) x = i * 2;
    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.

(Toggle Plain Text)

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.

 C Syntax (Toggle Plain Text) 
#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;
}
#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:

(Toggle Plain Text)

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!

(Toggle Plain Text)

#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)!

Jimbo · Apr 27th, 2008, 2:31 PM

Quote:

Originally Posted by Sane

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.

Sane · Apr 27th, 2008, 2:41 PM

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.

grumpy · Apr 28th, 2008, 4:46 AM

Quote:

Originally Posted by Sane

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.

opa6x57 · Apr 28th, 2008, 10:04 AM

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...

 VB Syntax (Toggle Plain Text) 
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
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...

 VB Syntax (Toggle Plain Text) 
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
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.

redfiretruck · Apr 28th, 2008, 12:34 PM

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

.

2 Quick Questions for now since they are on my mind

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?

Apr 27th, 2008, 2:20 PM	#5
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,869 Rep Power: 5	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: C Syntax (Toggle Plain Text) #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 << 1; return 0; } C Syntax (Toggle Plain Text) #include <stdio.h> int main() { unsigned i, x; for(i=1; i<1000000000; i++) x = i * 2; 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. (Toggle Plain Text) Coin: 1 2 3 4 5 6 7 8 Face: Tails Tails Heads Tails Heads Tails Heads Heads 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. C Syntax (Toggle Plain Text) #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; } #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: (Toggle Plain Text) 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 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! (Toggle Plain Text) #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; } #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)! __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data Last edited by Sane; Apr 27th, 2008 at 2:34 PM.

Apr 28th, 2008, 10:04 AM	#9
opa6x57 Hmmmm ... Is there more?? Join Date: Apr 2008 Location: Post Falls, ID Posts: 15 Rep Power: 0	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... VB Syntax (Toggle Plain Text) 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 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... VB Syntax (Toggle Plain Text) 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 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. __________________ Ken - New to PFO ... but been dabbling in various versions of BASIC since highschool - circa 1973. "Shouldn't the 'Air and Space' museum be empty?" - Dennis Miller

Apr 28th, 2008, 12:34 PM	#10
redfiretruck Newbie Join Date: Apr 2008 Posts: 23 Rep Power: 0	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 . 2 Quick Questions for now since they are on my mind 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?

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Interesting Bitwise tricks	Wizard1988	Coder's Corner Lounge	9	Nov 25th, 2007 7:09 PM
Bitwise Operator Question	grimpirate	PHP	1	Nov 13th, 2006 2:39 AM
Boolean operators??????	SpaderS	C++	4	Mar 20th, 2006 8:24 PM
bitwise operators and type double	ionexchange	C++	14	Feb 12th, 2006 9:27 AM
need help with bitwise operations	metsfan	C	17	Feb 2nd, 2006 6:09 PM

Apr 26th, 2008, 8:21 PM	#2
Jimbo Battle Programmer Join Date: Feb 2006 Location: Bellevue, WA, USA Posts: 763 Rep Power: 3	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: (Toggle Plain Text) 5 in binary is 00000101 shifted left twice is 00010100, which in decimal is 20 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) (Toggle Plain Text) -16 in binary is 11110000 shifted right two times is 11111100, which in decimal is -4 -16 in binary is 11110000 shifted right two times is 11111100, which in decimal is -4 132 >> 4 (arithmetic shift) (Toggle Plain Text) 132 in binary is 10000100 shifted right 4 times is 11111000, which in decimal is 248 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) (Toggle Plain Text) -16 in binary is 11110000 shifted right two times is 00111100, which in decimal is 60 -16 in binary is 11110000 shifted right two times is 00111100, which in decimal is 60 unsigned: 132 >> 4 (logical shift) (Toggle Plain Text) 132 in binary is 10000100 shifted right 4 times is 00001000, which in decimal is 16 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 (Toggle Plain Text) 11111111 & 10101010 -------- 10101010 11111111 & 10101010 -------- 10101010 240 & 31 == 0 (Toggle Plain Text) 11110000 & 00001111 --------- 00000000 11110000 & 00001111 --------- 00000000 here's how to check if a specific bit is set: 63 & (1 << 3) (Toggle Plain Text) 00111111 & 00001000 -------- 00001000 (which would be a true value) 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 (Toggle Plain Text) 01000000 \| 00100000 --------- 01100000 01000000 \| 00100000 --------- 01100000 129 \| 7 == 135 (Toggle Plain Text) 10000001 \| 00000111 -------- 10000111 10000001 \| 00000111 -------- 10000111 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 (Toggle Plain Text) 01000000 ^ 00100000 -------- 01100000 01000000 ^ 00100000 -------- 01100000 129 ^ 7 == 134 (Toggle Plain Text) 10000001 ^ 00000111 -------- 10000110 10000001 ^ 00000111 -------- 10000110 XOR can be used to toggle a bit, similar to the above ones. __________________ <insert disclaimer here> <insert shameless plug for Visual Studio here>

Apr 26th, 2008, 11:52 PM	#3
redfiretruck Newbie Join Date: Apr 2008 Posts: 23 Rep Power: 0	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 . 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

Apr 27th, 2008, 12:12 AM	#4
lectricpharaoh Caffeinated Neural Net Join Date: Jun 2005 Location: Dry west coast of Canada Posts: 1,031 Rep Power: 5	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: C Syntax (Toggle Plain Text) 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 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. __________________ And once again, Probability proves itself willing to sneak into a back alley and service Drama as would a copper-piece harlot. - Vaarsuvius, Order of the Stick

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C

Bitwise Operators...