When to use Logical vs. Bitwise Operator?

HelloWorld · #1 (**permalink**) 07-15-2007, 01:53 PM

I never used bitwise operator on my application, can anyone please help to open my eyes to when should I use bitwise operator for my application instead of logical operator...? and why?

I'm still kind of confused, when would I ever use single '&' instead of '&&' to create a comparison...

what's the difference between

Code:

if (x == 1 & x == 2) {
      .....
}

with

Code:

if (x == 1 && x == 2) {
     .....
}

I know what's the second one means though.. but what's the difference?

rpgfan3233 · #2 (**permalink**) 07-15-2007, 06:56 PM

Bitwise = manipulation (of numbers)
Logical = boolean test(s) of expression(s)

For example:

Code:

x = 4 | 1; //bitwise - results in 5 (0100 OR 0001 = 0101, which is 5)
if ((x == 4) || (x == 1)) { /* code */ } //logical - if x is 4 then the code is executed. if x is not 4, but x is 1 the code is executed. if x is neither 4 nor 1, the code is not executed.
if (((x & 4) != 0) || ((x & 1) != 0)) { /* code */ } //logical using bitwise operators - the bitwise AND returns a value of 4 if the bit at the 4s place (binary digit place) or 0 if the bit is not set. Next, you test that returned value to see if it is not 0. If it is not 0, then the code is executed. If it is 0, then the same process is repeated, but with "x & 1" instead of "x & 4".

Often bitwise operators are used to manipulate values, such as the following:

Code:

int INTENSITY = 0x8, RED = 0x4, GREEN = 0x2, BLUE = 0x1;
int MAGENTA = RED | BLUE;
int color = 9;
print_color(color);
color ^= RED; //if ((color & RED) == 0) color |= RED; else color -= RED;
print_color(color);

The output might look like this:
9
13

Or perhaps like this:
INTENSE BLUE
INTENSE MAGENTA

Either way, that shows how bitwise operators can be used to manipulate values. In fact, there is a technique using the bitwise XOR operator that sets a value to 0 quickly. The reason why it exists is due to Assembly programming, where MOV instructions can be somewhat costly at times, especially if you just wanted to change a value to 0. Here it is (the ^ character is the XOR operator:

Code:

variable_n ^= variable_n;

or

Code:

variable_n = variable_n ^ variable_n;

Why does this work? In terms of bits where the only possible values are 0 or 1, XOR checks to see if either bit is 1, but not both. If only one bit of the two compared bits are 1, the bit of the result at that bit place is set to 1. If both are 1 or neither are 1, the bit of the result at that bit place is 0.
With regards to this interesting trick, consider that variable_n = 14 (1110 in binary). Use XOR in binary on a single column at a time, and remember that 1 XOR 1 = 0 and 0 XOR 0 = 0:

Code:

    1110
XOR 1110
--------
    0000

Regarding your use of:

Code:

if (x == 1 & x == 2) // may act like "if (x == (1 & x) == 2)" or "if ((x == 1) & (x == 2))" depending on operator precedence in the language that you are using

vs

Code:

if (x == 1 && x == 2) // again, may act differently depending on operator precedence

you would only use "&&" for comparison. You would use "&" to operate on the values of "x == 1" and "x == 2", I'm guessing. Obviously, if you did that, it would basically be like saying "True AND False" or whatever, which may error out or it may convert True/False to integers and then perform the AND operation, which would result in 0 (False). In this example, it may have turned out the same either way, but with other examples (e.g. using different variables or performing operations on variables within the if statement) the result may not be the same.

TeraTask · #3 (**permalink**) 07-15-2007, 07:24 PM

Nice write up rpgfan3233. Let me expound on these 2 codes bases (adjusted for apparent intent and for additional complexity):

CONDITIONAL #1

Code:

if ((x == 1) & (x == 2) & (x == 3))

CONDITIONAL #2

Code:

if ((x == 1) && (x == 2) && (x == 3))

I will now answer your response by performing the necessary calculations for x = 3 (may not be 100% exact, but sufficiently so for this example):

CONDITIONAL #1 (assuming LTR processing)
REPLACE VALUES: if (( 3 == 1) & (3 == 2) & (3 == 3))
PERFOM EVALUATION: if (FALSE & (3 == 2) & (3 == 3))
PERFOM EVALUATION: if (FALSE & FALSE & (3 == 3))
PERFOM EVALUATION: if (FALSE & FALSE & TRUE)
PERFOM EVALUATION: if (FALSE & TRUE)
PERFOM EVALUATION: if (FALSE)

CONDITIONAL #2 (assuming LTR processing)
REPLACE VALUES: if (( 3 == 1) && (3 == 2) && (3 == 3))
PERFORM EVALUATION: if (FALSE && (3 == 2) && (3 == 3))

Why did Conditional #2 stop processing first? One of the conditions was false, so comparison was no longer necessary. Conditional #1 is like a long, binary mathematical statment. Conditional #2 is a logical comparison of individual comparisons. There's a slight difference there.

I have an article that should be out in about 4 hours (hopefully less), which will discuss a situation when using & can be helpful.

HelloWorld · #4 (**permalink**) 07-15-2007, 07:48 PM

Quote:

Here it is (the ^ character is the XOR operator

Thanx guys for all of the answer, really helpful to me to underestand it better. But I still have many more questions with this because I personally never encounter bitwise programming problems!!!

rpgfan, yes, I do remember that there's XOR operation, but I never used it. Why would you want to use that operation? Can you give me some examples?

What's the difference between '&' bitwise operator and '|' ??? I never used them all, like... at all.. never... so please guide me so that at least I can use them efficiently on a certain occassion

rpgfan3233 · #5 (**permalink**) 07-15-2007, 08:20 PM

The bitwise operators act the same way as their logical operator counterparts, except the bitwise operators work with each bit of a numeric value individually whereas a logical operator is used to work with true/false values.

XOR is good for a couple of things:

Fast way of changing an integer's value to zero (x ^= x; note I said "changing", not "setting". "changing" implies the idea that the value is already set ("int x = 4" for example) whereas "setting" can mean setting the value at any time, including initialization)
Simple Encryption/Decryption - What is XOR encryption?

Good for swapping values without a temporary variable:

Code:

int a = 2, b = 3;
print(a, b); //assuming there is a print() function available
a ^= b;
b ^= a;
a ^= b;
print(a, b);

As for the difference between '&' and '|', the difference is that the first is a bitwise AND operator and the second is a bitwise OR operator, just like "&&" is the logical AND operator and "||" is the logical OR operator.

Uses for AND '&':

Testing whether a specific bit is set, such as in a variable, where a specific bit represents a specific error code.

A faster version of the MOD operator '%' (n % m), where 'm' is a power of 2:

Code:

int n = 49;
print(n % 8);
print(n & 7); //the idea: n % m = n & (m - 1), where 'm' is a power of 2 (otherwise, it doesn't work)

Uses for OR '|':

Setting a specific bit, regardless of whether it is set or not set previously as in

Code:

int x = 9; /* 9 = 1001 */
print(x); //9
x |= 4;
print(x); //13, because the bit was not set
x |= 1;
print(x); //13, because the bit is already set

Adding powers of 2, such as 8 | 4 | 2 | 1 = 8+4+2+1 = 15. Note that it doesn't work for things like 9 | 8 | 1 because 9 = 8+1, which is 8 | 1. Because of that, you can say 9 | 8 | 1 = (8 | 1 | 8 | 1) = (8 | 1) = 9.

There is also the bitwise NOT operator, which reverses all bits, including the sign bit in signed numbers (in Java, numbers are always signed). I can't think of any uses that XOR wouldn't take care of. However, there was a use for it in Assembly programming. Rather than multiplying or dividing a value by -1 to simply change the sign of a value from positive to negative or from negative to positive, the NOT operator would be used, followed by an increment instruction. In C++ code, it looks like this:

Code:

//goal is to make x = -4
int x = 4;
print (x * -1); //-1
print ((~x) + 1); //-1, can also be print(++(~x)); I think

The boolean/logical NOT operator '!' is simply used to change from true(1) to false(0) and from false(0) to true(1). Note that "~0" = -1, whereas "!0" = 1.

HelloWorld · #6 (**permalink**) 07-15-2007, 08:52 PM

I tried the following code:

PHP Code:

  public class test1 {

    public static void main(String[] args) {

        int a = 1;

        int b = 2;

        System.out.println("a: " + a);

        System.out.println("b: " + b);

        a ^= b;

        System.out.println("a: " + a);

        System.out.println("b: " + b);

        b ^= a;

        System.out.println("a: " + a);

        System.out.println("b: " + b);

    }

}

I got this result:

Code:

a: 1
b: 2
a: 3
b: 2
a: 3
b: 1

Why is a become 3 while b becomes 1? Isn't it suppose to be 2 since you said that we don't need temp variable to swap...?

HelloWorld · #7 (**permalink**) 07-15-2007, 08:54 PM

Nevermind pal, I got it right, I tried it again by adding the last line...

Code:

		a ^= b;
		System.out.println("a: " + a);
		System.out.println("b: " + b);

I thought that line isn't critical, can you PLEASE explain me what just actually happened!!!??? I'm surprized!!!!

Do you think this is just exaclty the same if I use temp variable? Is it ok to use this swapping technique habitually...?

rpgfan3233 · #8 (**permalink**) 07-15-2007, 09:15 PM

Quote:

Originally Posted by HelloWorld

Nevermind pal, I got it right, I tried it again by adding the last line...

Code:

        a ^= b;
        System.out.println("a: " + a);
        System.out.println("b: " + b);

I thought that line isn't critical, can you PLEASE explain me what just actually happened!!!??? I'm surprized!!!!

What actually happened? Let's look at it.

a = 1, b = 2
In binary, a = 0001, b = 0010.

Now when we use XOR the first time:

Code:

a = a XOR b (a ^= b)
    0001  (a)
XOR 0010  (b)
--------
    0011

The result is 0011, or 3.
Now, a = 3 but b = 2 still because we haven't actually changed b yet.

Next XOR:

Code:

b = b XOR a (b ^= a)
    0010  (b)
XOR 0011  (a)
--------
    0001

The result is 0001, or 1. Since both bits were 1 in the 2s place this time, the result of the XOR operation on that pair of bits was 0. That leaves us with the 1 bit in the 1s place.
Now, a = 3 and b = 1. We've already got half of it done!

Final XOR:

Code:

a = a XOR b (a ^= b)
    0011  (a)
XOR 0001  (b)
--------
    0010

The result is 0010, or 2. Since both bits were 1 in the 1s place this time, the result of the XOR operation on that particular pair of bits was 0. That leaves us with the 1 bit in the 2s place.
The swap is done. a = 2 now, and b = 1 now.

HelloWorld · #9 (**permalink**) 07-15-2007, 09:20 PM

Trillion thanx a lot rpgfan, you're great! **can't give more than one thanx**

I learned a lot from your examples

BTW, you memorized all of the bit codes? 0001 or 1000 or 1100, etc? Do you think it's important to know at least some of them those are basics? also, is it a good habit to use this swapping system every time?

P.S sorry I've too many questions, that's cuz I'm really amazed to bit stuff now... lol...

rpgfan3233 · #10 (**permalink**) 07-15-2007, 10:08 PM

Bit codes are easy. You just have to know that it is all binary. For example, 16 = 2^4 (2 to the 4th power, not 2 XOR 4, in this case):
1*(2^4) + 0*(2^3) + 0*(2^2) + 0*(2^1) + 0*(2^0)
= 1*16 + 0*8 + 0*4 + 0*2 + 0*1
= 16 + 0 + 0 + 0 + 0
= 16

You see the x*(2^n) + y*(2^p) + ...? x and y are sometimes referred to as "coefficients". These coefficients are what makes up a binary number. In other words, you just write down the coefficients to make the number binary: 10000 = 16.

I suggest you check out Kingsley-Hughes.Com | Quick Binary Tutorial for more information. If that doesn't work for you, you can always just look for a different binary tutorial.

Edit: These are the ones I know by heart and can recite:
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536
That is the powers of 2 from 2^0 through 2^16.

I also know 4294967296 (2^32). I should really know 2147483648 (2^31) as well since the upper limit of an int in Java (or signed long int in C/C++) is 2147483647 (2^31 - 1). The upper limit of an unsigned long int in C/C++ is 4294967295 (2^32 - 1).

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

The Following 2 Users Say Thank You to rpgfan3233 For This Useful Post:
HelloWorld (07-15-2007), TeraTask (07-15-2007)

The Following User Says Thank You to TeraTask For This Useful Post:
HelloWorld (07-15-2007)

The Following 2 Users Say Thank You to rpgfan3233 For This Useful Post:
HelloWorld (07-15-2007), lwinaung (07-17-2008)

The Following User Says Thank You to rpgfan3233 For This Useful Post:
HelloWorld (07-15-2007)