• Advertisement

Archived

This topic is now archived and is closed to further replies.

Bitwise operators

This topic is 5064 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all, basically I''m just wondering whether it is necessary to know these (I was re-reading K&R''s C book just before and realised I have never used these operators... yet). i.e: & bitwise AND | bitwise inclusive OR ^ bitwise exclusive OR << left shift >> right shift ~ one''s complement (unary) Are these operators used often or rarely? (never by me :-) Can someone explain when you would be using these (or even better, recommend a book/site etc. that explains them in a bit more detail so I can get a better grasp on them). thanks in advance; any help appreciated :-)

Share this post


Link to post
Share on other sites
Advertisement
Well, one place I use them is in my compression code. Doing things like "add 4 bits to this stream" or "mask off bits 5-7" are easily handled with the bitwise operators. Another place they come in handy is while reading binary file formats (if bit n is high then we use full color...)

lonesock

Piranha are people too.

Share this post


Link to post
Share on other sites
I'd say it's very important you know these operators. They are used quite often actually. I'd say you'd see the shifts most often, following closely by bitwise AND and OR. Then comes exclusive OR, and finally the bitwise NOT (in my experience).

The shifts are used when you want to quickly multiply or divide by powers of 2, and when you want to, well, shift bits left and right, to get them into certain positions. You use the bitwise AND and OR most often to check and set bits in integers, and exclusive OR can be used to determine which bits are different between two integers (one of many usages). Bitwise NOT can be used to flip all the bits in an integer, although reasons for doing this vary.

These are all only some of the many usages of these operators. I'd recommend you get a more in-depth knowledge of how they actually work and what they do. I've found that MSDN has some really good explanations of these operators, but you can search around on the web for some other references.

[edited by - Zipster on April 10, 2004 4:11:47 AM]

Share this post


Link to post
Share on other sites
get to know these operators. you basically can''t live without them. usually these can get executed in one cpu cycle which is about as fast as is gets. you will need to know them if you do any API programming because, for example the winapi, uses the bitwise OR to concatenate flags you pass to api functions

Share this post


Link to post
Share on other sites
this depends on what you are programming,
and on your programming techniques.
for example vb dont have they operators,
and people are still living without them.
but its good to know them at least,
so that when you need one of them you will
recognize that.

most of their usage is when you want to encode
a state of something in a compact way.

for example lets say you want to encode a move on
chessboard with one 16-bit integer:

from: 0-7 (3-bits) , 0-7
to: 0-7 , 0-7

so you do this:
move = (fromx) | (fromy << 3) | (tox << 6) | (toy << 9)

thats the first thing that come to my mind about the use of shift
operators!!

to de-encode this use:
fromx = move & (1+2+4)
fromy = ( move << (16-6) ) >> (16-3)

note: 1+2+4 is eqivalent to: 0000 0000 0000 0111

these are most important techniques to use them.
still u can use four seperate integers to represent
the move. that depends on you.

sure many other uses are there, but my point is
if you dont know these operators,
you can never guess that you can encode a chessboard
move in one integer.

[edited by - zaidgs on April 10, 2004 5:41:32 PM]

Share this post


Link to post
Share on other sites
GameDev has an excellent article on this topic. I highly reccomend reading it. Once upon a time, when I was asking myself the same question you did, I learned almost everything I needed to know from this.

A more specific answer to your question: I used some of these operators recently in writing a function to convert from decimal integer to hexadecimal character. Check it out:


const char ToHex(int num, int index){

char digit = 0;

//we figure out one hex digit of the num

//specified by index. i.e. index 7 is the highest

//order hex digit, as in 0xF0000000 whereas index

//0 is lowest order, as in 0x0000000F

//The bitshifts move the isloated bits to the front

//of the number, in its lowest order, so it turns out

//to be a legitimate character.

switch(index){
case 0: digit = int(num & 0x0000000F); break;
case 1: digit = int((num & 0x000000F0) >> 4); break;
case 2: digit = int((num & 0x00000F00) >> 8); break;
case 3: digit = int((num & 0x0000F000) >> 12); break;
case 4: digit = int((num & 0x000F0000) >> 16); break;
case 5: digit = int((num & 0x00F00000) >> 20); break;
case 6: digit = int((num & 0x0F000000) >> 24); break;
case 7: digit = int((num & 0xF0000000) >> 28); break;
default: return 0;
}

//for the following, we must test the character as if

//it were a number in order to determine how to make

//it so that it is interpreted as the correct letter

//we want.

//

//OR a bitmask of 0011|0000 onto digit to make it alpha-numeric

if((digit >= 0) && (digit <= 9)) digit |= 0x30;

//OR a bitmask of 0100|0000 onto digit to make it alpha

else if((digit >= 10) && (digit <= 15)) (digit -= 9) |= 0x40;

else return 0; //error


return digit;
}

If you're a bit unclear on the OR's at the end of the ToHex() function, look up an ASCII code table and see the difference between the letter characters and the number characters. Look only at the hex values for each letter / digit. It is necessary to give the character the correct specifier bits on the high order of the character's byte so that they are interpreted correctly as a letter and not something else.

Now, imagine doing all that without bitwise operators... powerful, eh? I'll admit this isn't the most efficient way, but it certainly illustrates a good many uses of the most common bitwise operators.

EDIT: added comments to make code more clear

[edited by - MajorShredd on April 10, 2004 6:52:33 PM]

Share this post


Link to post
Share on other sites
Actually, even VB uses them. The obvious one is "if PlayerHealth <= 0 AND Lives = 0 then". However, when using the Win32 GDI, you need to know how masking works to perform transparent blitting.

Mask AND Screen
Sprite OR Screen

There''s an article on this, IIRC, but basically you''re switching off the bits you want to draw to, then switching them back on to the right color.

Share this post


Link to post
Share on other sites
"if PlayerHealth <= 0 AND Lives = 0 then" is not the same as "& bitwise AND"

VB AND = C/C++ &&

&& would be:
if(PlayerHealth <= 0 && Lives == 0)
{
//
}

//--------------------------------------------------------

& would be:

enum FLAGS
{
Flag1 = (1<<1),
Flag2 = (1<<2),
Flag3 = (1<<4)
};
//

void SomeFunction(int Flags = Flag1 | Flag2)
{
if(Flags & Flag1)
{
//Handle Flag1

}
//

if(Flags & Flag2)
{
//Handle Flag2

}
//

if(Flags & Flag3)
{
//Handle Flag3

}
}


-UltimaX-
Ariel Productions
|Designing A Screen Shot System|

"You wished for a white christmas... Now go shovel your wishes!"

Share this post


Link to post
Share on other sites
It''s very hard to avoid, at least bitwise or, if you are programming for windows. Many windows or directx functions requires some flags to be combined togheter, and that''s done with bitwise or.

Share this post


Link to post
Share on other sites
quote:
Original post by UltimaX
"if PlayerHealth <= = 0 AND Lives = 0 then" is not the same as "& bitwise AND"
Actually, it is. I didn't realize it for a long time, but VB doesn't have logical operators, only bitwise operators. So aside from shifting, which I suppose could be done with multiplication and integer division, VB has everything you need for bit manipulation. I wish I had known that on many previous occasions.

[edit]Well, I should add that in the original example, you would need parentheses around (PlayerHealth <= 0) and (Lives = 0), because since And is a bitwise operator, it evaluates before <= and = and other operators. Which sucks. And probably confuses plenty of people when they first learn VB, if they're use to something that does it differently, like C.[/edit]

[edited by - Agony on April 10, 2004 9:30:27 PM]

Share this post


Link to post
Share on other sites
Use it because it's FAST! using bitwise shift left is like multiplying by 2, but it's about 100 times faster than x * 2 (bitwise shift right for division). I use it in graphics code optimization.

The true general first seeks victory, then seeks battle
- Sun Tzu

[edited by - Drakkcon on April 10, 2004 10:12:16 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Agony
quote:
Original post by UltimaX
"if PlayerHealth <= = 0 AND Lives = 0 then" is not the same as "& bitwise AND"
Actually, it is. I didn''t realize it for a long time, but VB doesn''t have logical operators, only bitwise operators.

Are you sure? I always thought VB''s And/Or/Xor operators can be used in both situations and VB somehow does it automatically. If you use them in If..Then..Else statements, they would become logical operators. If you use them in numbers, they would become bitwise operators.

Share this post


Link to post
Share on other sites
VB''s And is overloaded, it behaves differently depending on the types. If you give it two longs it''s a bit and, it you give a boolean it''s a logical and.

And it has a lower precedence than < or >.

Share this post


Link to post
Share on other sites
quote:
Original post by Drakkcon
Use it because it''s FAST! using bitwise shift left is like multiplying by 2, but it''s about 100 times faster than x * 2 (bitwise shift right for division). I use it in graphics code optimization.

The true general first seeks victory, then seeks battle
- Sun Tzu

[edited by - Drakkcon on April 10, 2004 10:12:16 PM]


If the ''2'' is a constant, and your compiler can''t make that optimization for you, then your compiler sucks. :/

Share this post


Link to post
Share on other sites
quote:
Original post by Magmai Kai Holmlor
VB''s And is overloaded, it behaves differently depending on the types. If you give it two longs it''s a bit and, it you give a boolean it''s a logical and.
I don''t think that it''s operators are overloaded. What I think is really the case is that they make sure that True and False always have values that will make bitwise operators look like logicial operators. True is equal to -1, so assuming it''s a 16-bit integer, just like the Integer type, it would be 0xFFFF, and False is 0, thus 0x0000. Bitwise operators on those two values will be identical to logical operators. However, if you use something other than True or False, then you''ll no longer have something that looks like a logical operation, because in fact it never was. In C, && and || work with zero/non-zero numbers, which allows you to treat integers as though they were booleans, but in VB, you can never directly treat an integer as a simple boolean, because the operators work on a bitwise level, always. But as long as you stick with True and False, you''ll be good.

Share this post


Link to post
Share on other sites
Actually there are lots of reasons to know those operators and why they are neccessary.

1.) All operations in a computer can be done by three routines, shifting (left or right), Addition, and Mov (data movement and represented here by the mneumonic)

2.) If you can use bitwise manipulation on references you can swap pointers without a temporary, temp, variable like this:
x := x XOR y
y := x XOR y
x := x XOR y

Now x holds what y was and y holds what x was. The above reduces the cost of having another variable, and can allow the compiler to get more cache hits.

3.) XOR, and shift are used extensively for data compression and for color masking as in #2. The property mentioned in #2 where a variable can be packed with aother variable until unpacked is sometimes used for highlighting in some text editors, where the new color is XOR with the previous color until the hightlight is removed and then the undone by the above steps.

4.) You can copy a variable (if the language allows) with bitwise operators. For instance, say X is an integer, and Y is unitilized integer, then Y := X & 0xFFFFFFFF or Y := X & -1; will copy the value of X into Y, which will be true for pointer variables and for numeric variables as well.

5.) If you don''t know how bitwise operators work, then how are you going to understand debuggers because all addition is done in 2s compliment which would include unary negate operator.


BTW, 2 isn''t a constance from the above post its the base of binary, that''s why shift left and shift right divide and multiply by 2 (respectively) and so there are several other several bitwise (you might say tricks) but really they are based in computational theory.

" ''No one has control -- control is just a fantasy. And being human is difficult.'' "

Share this post


Link to post
Share on other sites
quote:
Original post by Lucidquiet
Actually there are lots of reasons to know those operators and why they are neccessary.

1.) All operations in a computer can be done by three routines, shifting (left or right), Addition, and Mov (data movement and represented here by the mneumonic)


"subtract and branch if negative" is sufficient on its own too (given appropriate addressing modes I guess). What''s your point?

quote:
2.) If you can use bitwise manipulation on references you can swap pointers without a temporary, temp, variable like this:
x := x XOR y
y := x XOR y
x := x XOR y

Now x holds what y was and y holds what x was. The above reduces the cost of having another variable, and can allow the compiler to get more cache hits.


It will completely destroy the compiler''s ability to parallelize the operation, however.

quote:
4.) You can copy a variable (if the language allows) with bitwise operators. For instance, say X is an integer, and Y is unitilized integer, then Y := X & 0xFFFFFFFF or Y := X & -1; will copy the value of X into Y, which will be true for pointer variables and for numeric variables as well.


Uh... "if the language allows" implies that we''re no longer talking just about C/C++, which in turn implies that bitwise operators do not necessarily even exist for us.

In C or C++, if X and Y are the same size type, then you''d just assign Y = X. If X is smaller (in terms of storage size - e.g. char vs int), it will be promoted automatically. If Y is smaller, then the implicit cast will already do the bitmasking that you propose. And pointer variables *are* numeric variables, at least in C and C++ where you can actually access them. Your AND-ing here doesn''t do anything except possibly discard signedness, which you should be able to do with an explicit (unsigned) cast anyway.

In Java, though, where both int and byte are signed types, you might occasionally find it useful to use "&255"''s on byte-packed data.

quote:
5.) If you don''t know how bitwise operators work, then how are you going to understand debuggers because all addition is done in 2s compliment which would include unary negate operator.


Uh, you don''t have to understand how the addition is done to see if the result is correct. The fact that numbers are represented in 2''s complement has nothing to do with bitwise operators. Unless maybe you want to forget that your CPU has a full adder installed and implement addition in software yourself? (There are "demonstrative" programming languages out there that force you to do it probably :/ )

quote:
BTW, 2 isn''t a constance from the above post its the base of binary, that''s why shift left and shift right divide and multiply by 2 (respectively) and so there are several other several bitwise (you might say tricks) but really they are based in computational theory.


... A constant. I.e., if you know at compile-time that you want to divide by 2, and not by any other number. The compiler, unless written by a sleep-deprived undergrad over the weekend, will see "DIV t1, 2" or equivalent in its "intermediate code", and automatically replace it with "RSHIFT t1, 1". Which lets you write the clear expression while netting the fast-running result. This is a Good Thing.

Share this post


Link to post
Share on other sites

  • Advertisement