Results 1 to 22 of 22

Thread: Bitwise operations

  1. #1
    Join Date
    Aug 2006
    Location
    London
    Posts
    2,021
    Mentioned
    2 Post(s)
    Quoted
    0 Post(s)

    Default Bitwise operations

    This is a tutorial about bitwise operators in computer languages. They can be very useful for calculations which require speed and a small amount of memory.

    Bits
    In bitwise operators, you will mostly have to think of numbers are the computer sees them, in bits, also called the binary system.
    To teach you that would take a whole tutorial of its own, but most people around here seem to know it already. If you dont know them, I suggest you find a tutorial or article to explain them, they are quite well known and will probably be easy to find.
    Find out why 1111 = 15, why 1001 = 9
    Note: For the purposes of this tutorial, all data types, such as byte, short and integer, are unsigned.

    Bitwise Shift
    These are probably the most well-known operations, what they do is simply shift bits around, they can be shift right, or shift left.

    In Scar and pascal, they are SHR (SHift Right) and SHL (SHift Left).
    In C-based languages, they are >> (shift right) and << (shift left)


    To get these, think of the bits, heres an example

    2 shl 1 = 4

    what is means is, the bits of 5, shifted to the left by 1, will give 10. See the bits table below

    0010 shl 1 = 0100

    as you can see, the bits have shifted to the left.


    Shift Right does the opposite, shifts every bit to the right

    8 shr 2 = 2

    1000 shr 2 = 0010

    So what do these mean for us? Well, shift-left multiplies the number by a power of 2, so shl 1 times by 2, shl 2 times by 4, shl 3 times by 8. That seems a bit useless, why not just do 2 * 2 = 4, well the answer is speed. Computers find it relativly difficult to multiply and add numbers, and relativly easy to shift bits around, bit-shifts are slightly faster than additions and much faster than multiplications. This is may not seem so important right now, but if you ever make a 3D flight simulator game, it will be very important when you have to update a few thousand pixels 25 times a second, you can only times and divide by powers of two, but if you use it in combination with adding at as well, it can still be faster. Another use for shifts is to combine numbers, such as two bytes can be made into a short integer, but we'll get to that later.

    Bitwise Or
    This is an operation which takes two number, and applies the OR logical operator on each bit.
    Note: do not confuse bitwise 'or' with boolean 'or', they are completely differant operations which just happen to have the same name.

    In scar and pascal, it is the same as the boolean or
    In C-based languages, it is | (verticle line or pipe)

    Look at this logical 'or' table
    0 or 1 -> 1
    1 or 0 -> 1
    1 or 1 -> 1
    0 or 0 -> 0

    Bitwise OR applies this table to every bit, heres an example.

    12 or 2 = 14

    1100 or 0010 = 1110

    Bitwise or is used to combine bits into one number, more on this later.


    Bitwise And
    This is an operation which takes two numbers, and applies the AND logical operator on each bit.

    In scar and pascal, it is the same as the boolean and
    In C-based languages, it is & ('and' sign or ampersand)

    Look at this logical 'and' table
    0 or 1 -> 0
    1 or 0 -> 0
    1 or 1 -> 1
    0 or 0 -> 0

    Bitwise AND applies this table to every bit, heres an example.

    12 and 9 = 8

    1100 and 1001 = 1000

    Bitwise or is used to separate bits from a number, more on this later.


    Example - Flags of an object
    Here's an example of using bitwise and and or.

    Lets say you're making an army game, where differant soldiers have differant qualifications, so one soldier can be able to use granades, also could handle an explosives kit, or perhaps a surface-to-air missile, or maybe be a medic. A soldier can be all these things at once, or non at all. Lets say you want to make a record of these skills, how would you do it?

    you could do it with a few booleans like this
    SCAR Code:
    type
      Soldier = record
      isGranader: boolean;
      canHandleExplosives: boolean;
      canUseSurfaceToAir: boolean;
      isMedic: boolean;
     end;

    it could also be an array, with each index carefully used.
    SCAR Code:
    type
      Soldier = record
      Skills:array[0..3] of boolean;
     end;

    //these are the indexes to use in the array
    const
     SkillGranader = 0;
     SkillExplosives = 1;
     SkillSurfaceToAir = 2;
     SkillMedic = 3;

    Then when you need to access the skill, you would do

    SCAR Code:
    if(mySoldier.Skills[SkillGranader])then
     Writeln('Its a granader!');


    Now the last way, which could be the most efficent, is to have each bit in a number represent a boolean.
    The idea is, you define a 'flag' to represent each skill, these flags have to have bits which are all zeros and one 1. See this example, the bit forms of the numbers are in comments.

    SCAR Code:
    const
     SkillGranader = 1;    //0001
     SkillExplosives = 2;  //0010
     SkillSurfaceToAir = 4;//0100
     SkillMedic = 8;       //1000

    in your record, you have one integer variable.
    SCAR Code:
    type
      Soldier = record
      Skills: integer;
     end;

    Lets say you want a soldier to have the skills of granader and medic, you would use the 'or' bitwise operator to combine the two values.

    SCAR Code:
    mySoldier.Skills := SkillGranader or SkillMedic;

    what that does to the bits is shown here.

    0001 or 1000 = 1001

    So thats the skills encoded, but how do you get them back out again? The answer is to use the bitwise 'and' operator. you need to 'and' the skills and the skill you want to test for, if the result is not zero, it means it is true, see the example.

    SCAR Code:
    function IsGranader(mySoldier : Soldier): Boolean;
    begin
    if(mySoldier.Skills and SkillGranader <> 0)
      Result:= True;
    end;

    what that does to the bits is shown here.

    1001 and 0001 = 0001

    1 is not equal to zero, so the Skills must contain SkillGranader, this is what happens if you test for a skill which isnt contained.

    1001 and 0100 = 0000

    the number returned is zero, so the skills do not contain SkillSurfaceToAir.

    The advantage to this method is the memory usage, in most languages, a boolean is stored in a byte, which contains 8 bits, but only 1 bit is used, 1 is true, 0 is false, so the other 7 bits are wasted. It is also useful for sending over a network, you can send 8 booleans in 1 byte, where as the other methods would have to send 8 bytes.


    Bitwise Not
    This is an operation which takes a number and reverses every bit

    In scar and pascal, it is the same as the boolean not
    In C-based languages, it is ~ (tidle)

    Look at this logical 'not' table
    0 not -> 1
    1 not -> 0

    Bitwise NOT applies this table to every bit, heres an example.

    12 not = 3

    1100 not = 0011


    Bitwise Xor
    This is an operation which takes two numbers, and applies the XOR logical operator on each bit.

    In scar and pascal, it is used with xor
    In C-based languages, it is ^ (caret)

    Look at this logical 'Xor' table
    0 or 1 -> 0
    1 or 0 -> 0
    1 or 1 -> 0
    0 or 0 -> 1

    Bitwise Xor applies this table to every bit, heres an example.

    12 or 9 = 7

    1100 or 1001 = 0111

    Its roughly equivalent to using bitwise or then bitwise not, but faster of course.


    Example - Colours in computers
    One place bitwise operators are always used is in encoding colours, you all know how in scar, colour is represented by a single integer from 0 to 16777215. Many of you also know that colour is actually represented as three bytes, from 0 to 255. So how does they get encoded into that big integer, the answer is with bitshifts. To encode a number, you leave the red alone, you shift the green 8 spaces, and the blue 16 spaces and 'or' all three numbers toghether. The bits of the colour end up looking like this.

    111100000000111111111111
    The red, green and blue components of this colour are 255, 15 and 240.
    The win32 integer representing this colour is 15732735, it is just one number, but it contains all three values,

    This is a function, written in scar, which changes RGB to win32 colour, I'm willing to bet about £5 that the identical function is in Scar.
    SCAR Code:
    function RGBToColor(r, g, b: Integer): Integer;
    begin
     Result:= (r) or (g shl 8) or (b shl 16);
    end;
    so now you have a number which can efficently be printed out, sent along a network or saved to file, but how do you separate the rgb components out again? Most people try reversing the bit-shifts, but that isnt enough, since its one number, not three. Look at this example.

    SCAR Code:
    //trying to get the green component
    15732735 shr 8 = 61455

    well the green component is not 61455 is it, this is because we kept the other bits as well, it works like this.

    11110000 00001111 11111111 shr 8 = 11110000 00001111

    what we have to do is to use the 'and' operator, we just want to cut out the last 8 bits, to do this, we need a number with the last 8 bits all filled, which happens to be 255. See the table.

    11110000 00001111
    and
    00000000 11111111
    =
    00000000 00001111
    (15)

    using 'and' 255 gives us 15, which is the correct green component.
    So the procedure is to do the reverse bit-shift, then and the return with 255.

    This is a procedure which changes win32 to RGB color, the one in Scar is probably the same.
    SCAR Code:
    procedure ColorToRGB(Color: Integer; var r, g, b: Integer);
    begin
     r:= (Color) and 255;
     g:= (Color shr 8) and 255;
     b:= (Color shr 16) and 255;
    end;


    And that is all I have to show you about bitwise operators, I know I ran over the part about xor and not, but I just never really saw them being used for anything.
    Join the Official SRL IRC channel. Learn how to Here.

  2. #2
    Join Date
    May 2006
    Location
    Amsterdam
    Posts
    3,620
    Mentioned
    5 Post(s)
    Quoted
    0 Post(s)

    Default

    Nice! Thank you! _o_
    Verrekte Koekwous

  3. #3
    Join Date
    Feb 2006
    Location
    Amsterdam
    Posts
    13,691
    Mentioned
    146 Post(s)
    Quoted
    130 Post(s)

    Default

    Still reading..



    The best way to contact me is by email, which you can find on my website: http://wizzup.org
    I also get email notifications of private messages, though.

    Simba (on Twitter | Group on Villavu | Website | Stable/Unstable releases
    Documentation | Source | Simba Bug Tracker on Github and Villavu )


    My (Blog | Website)

  4. #4
    Join Date
    Dec 2006
    Location
    Copy pastin to my C#
    Posts
    3,788
    Mentioned
    8 Post(s)
    Quoted
    29 Post(s)

    Default

    Im a little confused =/

    Great tutorial, but I didnt understand too much.

    A bit I understood with experimenting with scar, but maybe I should look more into binary and then read again.

    EDIT: o, no.
    Get ready for the coolest tutorials in town... This is where we seperate the men from the boys!!!
    Back to reading

    EDIT EDIT: Wait a second, I experimented shl in scar, and is it " x shl x = x+x * x"?

    EDIT EDIT EDIT: Yes it is! Wh0000!

  5. #5
    Join Date
    Nov 2006
    Posts
    1,103
    Mentioned
    0 Post(s)
    Quoted
    6 Post(s)

    Default

    this is just like logic electronics, thanks i can use this for sure
    Infractions, reputation, reflection, the dark side of scripting, they are.

  6. #6
    Join Date
    Jan 2007
    Location
    USA
    Posts
    1,782
    Mentioned
    0 Post(s)
    Quoted
    0 Post(s)

    Default

    Thanks Yakman. Great tut

    Join the fastest growing merchanting clan on the the net!

  7. #7
    Join Date
    Feb 2006
    Location
    Amsterdam
    Posts
    13,691
    Mentioned
    146 Post(s)
    Quoted
    130 Post(s)

    Default

    Quote Originally Posted by n3ss3s View Post
    EDIT EDIT EDIT: Yes it is! Wh0000!
    4 shl 4 = 4 * 2 * 2 * 2 * 2.
    32 shr 4 = 32 / 2 / 2 / 2 / 2.



    The best way to contact me is by email, which you can find on my website: http://wizzup.org
    I also get email notifications of private messages, though.

    Simba (on Twitter | Group on Villavu | Website | Stable/Unstable releases
    Documentation | Source | Simba Bug Tracker on Github and Villavu )


    My (Blog | Website)

  8. #8
    Join Date
    Jun 2006
    Posts
    3,861
    Mentioned
    3 Post(s)
    Quoted
    0 Post(s)

    Default

    Thanks very much! I understood all of it

    *impresses friends with 1337 skillz

  9. #9
    Join Date
    Dec 2006
    Location
    utah
    Posts
    1,427
    Mentioned
    2 Post(s)
    Quoted
    7 Post(s)

    Default

    Thanks, great tut! anyway i saw one like this some where around by benland
    Co Founder of https://www.tagcandy.com

  10. #10
    Join Date
    Dec 2006
    Location
    Banville
    Posts
    3,914
    Mentioned
    12 Post(s)
    Quoted
    98 Post(s)

    Default

    ^.^ Great job, you taught me something! (Thats pretty new, actually...)
    The jealous temper of mankind, ever more disposed to censure than
    to praise the work of others, has constantly made the pursuit of new
    methods and systems no less perilous than the search after unknown
    lands and seas.

  11. #11
    Join Date
    Nov 2006
    Posts
    1,103
    Mentioned
    0 Post(s)
    Quoted
    6 Post(s)

    Default

    i just found something nice, untill now i always used 'X mod 2' to decide weather something is even or uneven, but try using 'X and 1'
    Infractions, reputation, reflection, the dark side of scripting, they are.

  12. #12
    Join Date
    Apr 2007
    Location
    The Netherlands
    Posts
    5,553
    Mentioned
    0 Post(s)
    Quoted
    0 Post(s)

    Default

    nice dont understand the most :s
    ~Hermen

  13. #13
    Join Date
    Oct 2006
    Posts
    1,071
    Mentioned
    0 Post(s)
    Quoted
    1 Post(s)

    Default

    Wow I never knew any of this, and I only understood like 75% of it, but still, great tut Yakman! Thanks!

  14. #14
    Join Date
    Jan 2007
    Location
    Kansas
    Posts
    3,760
    Mentioned
    1 Post(s)
    Quoted
    3 Post(s)

    Default

    Very nice, understand it for the most part.


  15. #15
    Join Date
    Feb 2006
    Location
    Belgium
    Posts
    3,137
    Mentioned
    3 Post(s)
    Quoted
    5 Post(s)

    Default

    hey, sorry for the bump, but I believe that shr is >>> in c++, there no delphi keyword for >>, though in asm it'd be "sar"

  16. #16
    Join Date
    May 2006
    Location
    Amsterdam
    Posts
    3,620
    Mentioned
    5 Post(s)
    Quoted
    0 Post(s)

    Default

    Quote Originally Posted by Freddy1990 View Post
    hey, sorry for the bump, but I believe that shr is >>> in c++, there no delphi keyword for >>, though in asm it'd be "sar"
    No.. In ASM It would be SHR to... SAR also swifts the CF Flag..

    http://www.geocities.com/SiliconVall...rsrc/asmsh.htm
    Verrekte Koekwous

  17. #17
    Join Date
    Feb 2006
    Location
    Belgium
    Posts
    3,137
    Mentioned
    3 Post(s)
    Quoted
    5 Post(s)

    Default

    I don't recall saying that sar and shr are the same
    I said that >> is the same as sar and that >>> the same is as shr

  18. #18
    Join Date
    May 2006
    Location
    Amsterdam
    Posts
    3,620
    Mentioned
    5 Post(s)
    Quoted
    0 Post(s)

    Default

    Quote Originally Posted by Freddy1990 View Post
    I don't recall saying that sar and shr are the same
    I said that >> is the same as sar and that >>> the same is as shr
    Then like always, i misread
    Verrekte Koekwous

  19. #19
    Join Date
    Feb 2006
    Location
    Belgium
    Posts
    3,137
    Mentioned
    3 Post(s)
    Quoted
    5 Post(s)

    Default

    Heh, np, spent some time messing with that when I was working on a project that I never finished... I needed all 3 c++ operators and I couldn't figure out where the third was in delphi, so I did some research... (Assuming I'm correct of course )

  20. #20
    Join Date
    Dec 2006
    Location
    Banville
    Posts
    3,914
    Mentioned
    12 Post(s)
    Quoted
    98 Post(s)

    Default

    << and >> are the shifts in C++.


    If there is a SAR in C++, it might be >>> or <<<.
    The jealous temper of mankind, ever more disposed to censure than
    to praise the work of others, has constantly made the pursuit of new
    methods and systems no less perilous than the search after unknown
    lands and seas.

  21. #21
    Join Date
    Jul 2007
    Posts
    1,431
    Mentioned
    0 Post(s)
    Quoted
    0 Post(s)

    Default

    Now, this has to be bumped, this one...nice...Yakman is smart.
    Got answer for most of my painful questions about math.
    [CENTER][SIZE="4"]Inactive[/SIZE]I forgot my password[/CENTER]

  22. #22
    Join Date
    Nov 2007
    Location
    46696E6C616E64
    Posts
    3,069
    Mentioned
    44 Post(s)
    Quoted
    302 Post(s)

    Default

    This got me interested, as I have been doing some image manipulation in PHP whenever I have some time.

    Made some functions (ColorToRGB and RGBToColor are straight from here, converted to PHP only.):
    PHP Code:
    function ColorToRGB($color, &$r, &$g, &$b) {
        
    $r $color 255;
        
    $g = ($color >> 8) & 255;
        
    $b = ($color >> 16) & 255;
    }

    function 
    RGBToColor($r$g$b) {
        return 
    $r | ($g << 8) | ($b << 16);
    }

    function 
    InvertRGB(&$r, &$g, &$b) {
        
    $r = (255 $r);
        
    $g = (255 $g);
        
    $b = (255 $b);
    }

    function 
    InvertColor($color) {
        
    $r $color 255$g = ($color >> 8) & 255$b = ($color >> 16) & 255;
        
    $r = (255 $r); $g = (255 $g); $b = (255 $b);
        return 
    $r | ($g << 8) | ($b << 16);

    Heres the output:

    And url: http://www.frement.net/rgb.php?color=16711680
    There used to be something meaningful here.

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. In-depth Bitwise Operators.
    By R0b0t1 in forum OSR Advanced Scripting Tutorials
    Replies: 3
    Last Post: 09-02-2008, 06:32 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •