| View previous topic :: View next topic |
| Author |
Message |
Aviar³
Grandmaster Cheater
 Reputation: 50
Joined: 03 Jan 2008
Posts: 655
Location: Canada
|
 Posted: Mon Sep 14, 2009 9:21 am Post subject: Bitwise operators |
 |
|
Never could find any decent article that explained the bitwise operators. Book I read simply glazed over them. Anyone know an article that will explain how they truly operate, and possible applications?
| The C Programming Language Second Edition wrote: |
2.9 Bitwise Operators
C provides six operators for bit manipulation; these may only be applied to integral operands, that is, char, short, int, and long, whether signed or unsigned.
&
bitwise AND
|
bitwise inclusive OR
^
bitwise exclusive OR
<<
left shift
>>
right shift
~
one's complement (unary)
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.
The bitwise OR operator | is used to turn bits on:
x = x | SET_ON;
sets to one in x the bits that are set to one in SET_ON.
The bitwise exclusive OR operator ^ sets a one in each bit position where its operands have different bits, and zero where they are the same. |
_________________
This is the inception of deception, checking the depth of your perception.
 |
|
| Back to top |
|
 |
DoomsDay
Grandmaster Cheater
 Reputation: 0
Joined: 06 Jan 2007
Posts: 768
Location: %HomePath%
|
|
| Back to top |
|
|
Aviar³
Grandmaster Cheater
Reputation: 50
Joined: 03 Jan 2008
Posts: 655
Location: Canada
|
| Posted: Mon Sep 14, 2009 9:47 am Post subject: |
|
|
| DoomsDay wrote: | | http://en.wikipedia.org/wiki/Bitwise_operation |
Touche.
_________________
This is the inception of deception, checking the depth of your perception.
|
|
| Back to top |
|
|
kot1990
Expert Cheater
 Reputation: 1
Joined: 06 Sep 2009
Posts: 131
Location: Greece
|
| Posted: Mon Sep 14, 2009 10:56 am Post subject: |
|
|
That might be helpful. It explains every operator with an example:
http://www.codeproject.com/KB/cpp/bitbashing.aspx
Last edited by kot1990 on Mon Sep 14, 2009 2:22 pm; edited 3 times in total |
|
| Back to top |
|
|
hcavolsdsadgadsg
I'm a spammer
![]() Reputation: 26
Joined: 11 Jun 2007
Posts: 5801
|
| Posted: Mon Sep 14, 2009 11:15 am Post subject: |
|
|
| Aviar wrote: | | DoomsDay wrote: | | http://en.wikipedia.org/wiki/Bitwise_operation |
Touche. |
eh, that is basically all there is to it.
convert your number to binary if you really feel so inclined in windows calculator then mess around with them.
As for applications... I guess alpha blending in graphics makes sense.
The formula is:
| Code: | | (alpha * (color - background)) / 255 + background |
Say you have a 32 bit color. It's expressed in a DWORD like 0xXXRRGGBB
Say we wanted to draw the color 0x00FFAAFF, a whitish pink.
A common trick is to shift right 8 (>> 8 ) to replace the need to divide by 255. Furthermore is the reason that the "overflow" like 0xFF * 128 = 0x7F80, aka out of the realm of 1 byte, the need to split it up comes in, unless you like botched results.
If you wanted to draw a pixel with the color of 0x00FFAAFF, a whitish pink on a black backround with an alpha of 128, it would look like...
(pixel we're drawing) 0x00FFAAFF - 0x00000000 (backround)
nothing changed, obviously.
0x00FFAAFF * 128 = 0x7FD57F80
0x7FD57F80 / 256 = 0x007FD57F (AKA COMPLETELY WRONG)
what's a simple way to split it up? bitwise and, which is useful for masking operations.
| Code: | 0101
0011
------
0001 |
0x00FFAAFF looks like:
00000000 - 11111111 - 10101010 - 11111111
0x00FF00FF:
00000000 - 11111111 - 00000000 - 11111111
look at it carefully and it should make sense... maybe.
| Code: | DWORD ag = 0x00FFAAFF & 0xFF00FF00;
DWORD rb = 0x00FFAAFF & 0x00FF00FF; |
like magic, ag only contains 0x0000AA00.
rb only contains 0x00FF00FF.
Now we have room to go nuts and we can just mask off whatever later.
Ok, cool, how do we get them back together?
Just bitwise or it.
result = (ag | rb);
0101
0011
-----
0111
0x00FF00FF looks like:
00000000 - 11111111 - 00000000 - 11111111
0x0000FF00:
00000000 - 00000000 - 11111111 - 00000000
I'm sure you can deduct what or'ing them will do.
Holy shit long post, but there is your example.
Last edited by hcavolsdsadgadsg on Mon Sep 14, 2009 12:08 pm; edited 2 times in total |
|
| Back to top |
|
|
Aviar³
Grandmaster Cheater
Reputation: 50
Joined: 03 Jan 2008
Posts: 655
Location: Canada
|
| Posted: Mon Sep 14, 2009 11:49 am Post subject: |
|
|
I have seen pretty neat applications of binary operators. Main reason they interest me is because they are commonly used to optimize code (at sacrifice of readability).
_________________
This is the inception of deception, checking the depth of your perception.
|
|
| Back to top |
|
|
hcavolsdsadgadsg
I'm a spammer
![]() Reputation: 26
Joined: 11 Jun 2007
Posts: 5801
|
| Posted: Mon Sep 14, 2009 12:08 pm Post subject: |
|
|
| edited my post above, that seems like what you have in mind. |
|
| Back to top |
|
|
Guy
Expert Cheater
![]() Reputation: 0
Joined: 30 May 2009
Posts: 187
|
| Posted: Mon Sep 14, 2009 4:43 pm Post subject: |
|
|
It should be noted, you can replace arithmetic operators using bitwise operators, and in some cases, it usually can be faster.
For example, taken from my VM for adding two numbers:
| Code: |
void Chameleon::add( REGISTER volatile *vmRegister, unsigned long volatile vmValue )
{
*vmRegister = ( *vmRegister ^ vmValue ) | ( ( *vmRegister & vmValue ) << 1 );
if( vmValue < 0xFF )
vmContext.ip += 2;
else
vmContext.ip += 1 + sizeof( vmValue );
}
|
Note the use of the XOR operator, OR operator, the AND operator, and the shift left operator. Whether or not that's actually faster is unknown (In this instance, I'd believe it to be slower).
_________________
Has anyone seen Hitler around..? If so, PM me! |
|
| Back to top |
|
|
DoomsDay
Grandmaster Cheater
Reputation: 0
Joined: 06 Jan 2007
Posts: 768
Location: %HomePath%
|
| Posted: Tue Sep 15, 2009 1:50 am Post subject: |
|
|
| Guy` wrote: | It should be noted, you can replace arithmetic operators using bitwise operators, and in some cases, it usually can be faster.
For example, taken from my VM for adding two numbers: | Code: |
void Chameleon::add( REGISTER volatile *vmRegister, unsigned long volatile vmValue )
{
*vmRegister = ( *vmRegister ^ vmValue ) | ( ( *vmRegister & vmValue ) << 1 );
if( vmValue < 0xFF )
vmContext.ip += 2;
else
vmContext.ip += 1 + sizeof( vmValue );
}
|
Note the use of the XOR operator, OR operator, the AND operator, and the shift left operator. Whether or not that's actually faster is unknown (In this instance, I'd believe it to be slower). |
This kind of addition is recursive... You're handling just the first carry (add 0x01 to 0xFF and you'l get 0xFE). | Code: | | ADD(A,B) = ((A & B) ? ADD((A^B),(A&B << 1)) : A) |
AFAIK, there is no speed gain for most replacements (That depends on the CPU ofcourse). Applications? a lot of hashing algorithms (CRC for example) rely on bitwise operators. |
|
| Back to top |
|
|
hcavolsdsadgadsg
I'm a spammer
![]() Reputation: 26
Joined: 11 Jun 2007
Posts: 5801
|
| Posted: Tue Sep 15, 2009 9:42 am Post subject: |
|
|
I wouldn't doubt if the compiler was smart enough to do almost all those gimmicky tricks.
Even with optimizations off, MSVC generated a bitwise (replacing my modulo) and to check for odd / even. This is a pretty spame optimization, I'm sure, but you generally shouldn't be trying to outsmart your compiler unless your job is to write savagely optimized raytracers or some shit. |
|
| Back to top |
|
|
igoticecream
Grandmaster Cheater Supreme
 Reputation: 0
Joined: 23 Apr 2006
Posts: 1807
Location: 0x00400000
|
| Posted: Tue Sep 15, 2009 6:57 pm Post subject: |
|
|
You need to know about truth table:
AND (conjuntion): //When both are true
1^1=1
1^0=0
0^1=0
0^0=0
OR (disjuntion): //When one of the member is true (could be both)
1v1=1
1v0=1
0v1=1
0v0=0
XOR (Exclusive disjuntion): //When one is true and the other one is false
1⊕1=0
1⊕0=1
0⊕1=1
0⊕0=0
Also the unary operator NOT: //just reverse the boolean value
¬1=0
¬0=1 |
|
| Back to top |
|
|
Guy
Expert Cheater
![]() Reputation: 0
Joined: 30 May 2009
Posts: 187
|
| Posted: Tue Sep 15, 2009 7:02 pm Post subject: |
|
|
| slovach wrote: | I wouldn't doubt if the compiler was smart enough to do almost all those gimmicky tricks.
Even with optimizations off, MSVC generated a bitwise (replacing my modulo) and to check for odd / even. This is a pretty spame optimization, I'm sure, but you generally shouldn't be trying to outsmart your compiler unless your job is to write savagely optimized raytracers or some shit. |
The idea was for obfuscation purposes in that instance, not necessarily speed.
_________________
Has anyone seen Hitler around..? If so, PM me! |
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
