AlliedModders - [INFO] Bitsums and Operators

AlliedModders (https://forums.alliedmods.net/index.php)

- Code Snippets/Tutorials (https://forums.alliedmods.net/forumdisplay.php?f=83)

- - [INFO] Bitsums and Operators (https://forums.alliedmods.net/showthread.php?t=90507)

[INFO] Bitsums and Operators

About:
This tutorial is meant for beginner scripters from amxx. This will teach you on how to use bitsum operators and show some advantages over boolean storage arrays!

What is a bitsum?
A bitsum is based on the way memory works. If we think, the memory chip containes cells (bits) that can hold 2 infos: 1 and 0. To store a number in one byte (byte = 8 bits) here is how to do it:
"8" (normal number) = "00001000" (memory number [1 byte])

How does a bitsum work?
Well the idea is that bitsums allow to control the position that we want to set it to 1. And we can check wether that position has 1 or 0.

What operators do I have, and what do they mean?
I will give an example for each operator:

PHP Code:


		
			
Operator: |

first_byte = "10010001"

second_byte = "01010001"



first_byte | second_byte = "11010001"

So basically this operator works like the logical one || but it does the operation on each bit!

Code:

|     1      0

1     1      1

0     1      0

PHP Code:


		
			
Operator: &

first_byte = "10010001"

second_byte = "01010001"



first_byte & second_byte = "0001001"

So basically this operator works like the logical one && but it does the operation on each bit!

Code:

&     1      0

1     1      0

0     0      0

PHP Code:


		
			
Operator: ^ (Exclusive OR)

first_byte = "10010001"

second_byte = "01010001"



first_byte ^ second_byte = "1100000"

So basically this operator works like the logical one ^^ but it does the operation on each bit!

Code:

^    1      0

1    0      1

0    1      0

PHP Code:


		
			
Operator: ~ (Complement applies on only one number!)

first_byte = "10010001"



~first_byte = "01101110"

So basically this operator negates every bit! So 0 becomes 1 and 1 becomes 0.

Code:

~1 = 0

~0 = 1

How do normal numbers work?
They are stored in the normal cells by base. So they are converted from base 10 from base 2. In this case number 9 for example becomse: "00001001". To comvert that number from the cells back to 9 we need to multiply each position with 2 and a power of it! 2^2 = power(2,2) = 4
00001001: 1*(2^0) + 0*(2^1) + 0*(2^2) + 1*(2^3) + 0*(2^4) + 0*(2^5) + 0*(2^6) + 0*(2^7) = 1 + 8 = 9

How can I easily create a bitsum?
Well you need 2 operators: << and >>, or if you don't want to use those operators you can easily create one by using elements that represent powers of 2.
Example:

PHP Code:


		
			
Bitsum "00001111" = 8 | 4 | 2 | 1

The 2 operators have a special meaning!
"<< x" means that a position of a number is moved by x points to left! Example:

PHP Code:


		
			
"00001100" << 1 = "00011000"

When we convert this to normal number we can see that the normal number was multiplied by 2.
So if we have (1<<3) it would be like 2^3 * 1

The >> operator does the same thing like << but moves x points to right! When using integer variables the numbers disappear.

PHP Code:


		
			
"00000111" >> 3 = "00000000"

So using those 2 operators to create a bitsum we have this:

PHP Code:


		
			
Bitsum "00001111" = (1<<3 | 1<<2 | 1<<1 | 1<<0)

How can I use this in my scripts?
Well it can be used for insance instead of boolean arrays.

So instead of having this:

PHP Code:


		
			
new bool:is_alive[33]

We have:

PHP Code:


		
			
new bitsum_is_alive

So less memory usage!

Instead of

PHP Code:


		
			
if (is_alive[id])

{

}

We have:

PHP Code:


		
			
if (bistum_is_alive & (1<<id))

{

}

Instead of this

PHP Code:


		
			
is_alive[id] = true

PHP Code:


		
			
is_alive[id] = false

We will have this:

PHP Code:


		
			
bitsum_is_alive |= (1<<id)

PHP Code:


		
			
bitsum_is_alive &=  ~(1<<id)

The good thing is that you can extend the limit of the 32 slots that a simple number allowes with an array so that we can have more slots.
Ex:

PHP Code:


		
			
new holder[4]

// holder has 4 * 32 places where we can store the true/false value

// Here are the functions that allow you to manipulate them!



// Here we make the desired slot true

save(x)

{

    holder[x / 32] |= 1 << (x % 32);

}



// Here we check the desired slot 

exists(x)

{

    return holder[x / 32] & 1 << (x % 32);

}

 

// Here we remove the desired slot 

remove(x)

{

    holder[x / 32] &= ~(1 << (x % 32))

}

As you can see it is harder to use bitsums but they have better results when it comes to low memory usage!
Hope that my english was fine!

Re: [INFO] Bitsums and Operators

Wow thx for Great TUT!

Quote:

Originally Posted by ot_207 (Post 809152)

So less memory usage!

Profiled:

Code:

date: Sun Apr 19 15:20:28 2009 map: de_dust

type |                             name |      calls | time / min / max

-------------------------------------------------------------------

   n |                   register_clcmd |          2 | 0.000019 / 0.000004 / 0.000015

   p |                       array_test |         10 | 0.064196 / 0.006202 / 0.006642

   p |                      bitsum_test |         10 | 0.029594 / 0.002811 / 0.003570

   p |                      plugin_init |          1 | 0.000002 / 0.000002 / 0.000002

0 natives, 0 public callbacks, 3 function calls were not executed.

Tested on this code:

PHP Code:


		
			
#include <amxmodx>



new array[33]

new bitsum



public plugin_init() 

{

    array[32] = false

        

    bitsum &=  ~(1<<32) 

    

    register_clcmd("array","array_test")

    register_clcmd("bitsum","bitsum_test")

}



public bitsum_test()

{

    for(new i;i<=1_000_000;i++)

        if(bitsum & (1<<32))

            continue;

}



public array_test()

{

    for(new i;i<=1_000_000;i++)

        if(array[32])

            continue;

}

Now I'm thinking should I swap arrays with bitsums in my plugins code. It would use less memory, but it will be harder to understand the code.

Re: [INFO] Bitsums and Operators

Thanks for profiling this :) and for having the patience to read it :wink:.
Indeed it will be harder to understand the code but you can also do some stocks that will make it easier to read :).

Re: [INFO] Bitsums and Operators

Quote:

Originally Posted by ot_207 (Post 809296)

you can also do some stocks that will make it easier to read :).

Wow! Thats interesting.
Can you give an example of such a stock?

Re: [INFO] Bitsums and Operators

Example:

PHP Code:


		
			
stock is_user_alive(id)

{

      return (bistum_is_alive & (1<<id)) ? 1 : 0

}

Or macro:

PHP Code:


		
			
#define is_user_alive(%1) (bistum_is_alive & (1 << %1)) ? 1 : 0

Re: [INFO] Bitsums and Operators

Macro is more appropriate here. Also you can do something that to return 0 or 1.

Code:

#define is_user_alive(%1) !!(bistum_is_alive & (1 << %1))

Re: [INFO] Bitsums and Operators

Quote:

Originally Posted by Empowers (Post 809286)

Wow thx for Great TUT!

Profiled:

Code:



        Code:


        
date: Sun Apr 19 15:20:28 2009 map: de_dust

type |                             name |      calls | time / min / max

-------------------------------------------------------------------

   n |                   register_clcmd |          2 | 0.000019 / 0.000004 / 0.000015

   p |                       array_test |         10 | 0.064196 / 0.006202 / 0.006642

   p |                      bitsum_test |         10 | 0.029594 / 0.002811 / 0.003570

   p |                      plugin_init |          1 | 0.000002 / 0.000002 / 0.000002

0 natives, 0 public callbacks, 3 function calls were not executed.


Tested on this code:



        PHP Code:


        

                


                

                

                        

#include <amxmodx>new array[33]new bitsumpublic plugin_init() {    array[32] = false            bitsum &=  ~(1<<32)         register_clcmd("array","array_test")    register_clcmd("bitsum","bitsum_test")}public bitsum_test(){    for(new i;i<=1_000_000;i++)        if(bitsum & (1<<32))            continue;}public array_test(){    for(new i;i<=1_000_000;i++)        if(array[32])            continue;} 







                


                

                


        


Now I'm thinking should I swap arrays with bitsums in my plugins code. It would use less memory, but it will be harder to understand the code.

That profile is wrong.

PHP Code:


		
			
#include <amxmodx>

new array[3]
new bitsum

public Index(n)
{
    return array[n]
}

public Bit(n)
{
    return (bitsum & (1<<n))
}

public plugin_cfg()
{
    array[1] = true
    bitsum   = (1 << 1) 
    
    for(new i;i<10000;i++)
    {
        Bit(1)
        Index(1);
        Bit(2);
        Index(2);
    }
    
    server_cmd("quit");
}

HTML Code:

date: Sun Apr 19 08:56:46 2009 map: de_dust2

type |                             name |      calls | time / min / max

-------------------------------------------------------------------

   n |                       server_cmd |          1 | 0.000013 / 0.000013 / 0.000013

   p |                       plugin_cfg |          1 | 0.088612 / 0.088612 / 0.088612

   f |                              Bit |      20000 | 0.043302 / 0.000001 / 0.000040

   f |                            Index |      20000 | 0.043490 / 0.000001 / 0.000104

0 natives, 2 public callbacks, 1 function calls were not executed.



date: Sun Apr 19 08:57:13 2009 map: de_dust2

type |                             name |      calls | time / min / max

-------------------------------------------------------------------

   n |                       server_cmd |          1 | 0.000012 / 0.000012 / 0.000012

   p |                       plugin_cfg |          1 | 0.094011 / 0.094011 / 0.094011

   f |                              Bit |      20000 | 0.045281 / 0.000001 / 0.000012

   f |                            Index |      20000 | 0.046318 / 0.000001 / 0.000488

0 natives, 2 public callbacks, 1 function calls were not executed.



date: Sun Apr 19 08:57:20 2009 map: de_dust2

type |                             name |      calls | time / min / max

-------------------------------------------------------------------

   n |                       server_cmd |          1 | 0.000016 / 0.000016 / 0.000016

   p |                       plugin_cfg |          1 | 0.092532 / 0.092532 / 0.092532

   f |                              Bit |      20000 | 0.044500 / 0.000001 / 0.000023

   f |                            Index |      20000 | 0.044818 / 0.000001 / 0.000137

0 natives, 2 public callbacks, 1 function calls were not executed.



date: Sun Apr 19 08:57:28 2009 map: de_dust2

type |                             name |      calls | time / min / max

-------------------------------------------------------------------

   n |                       server_cmd |          1 | 0.000014 / 0.000014 / 0.000014

   p |                       plugin_cfg |          1 | 0.095900 / 0.095900 / 0.095900

   f |                              Bit |      20000 | 0.045795 / 0.000001 / 0.000194

   f |                            Index |      20000 | 0.045659 / 0.000001 / 0.000117

0 natives, 2 public callbacks, 1 function calls were not executed.

Bitsums can't be used to replace is_user_alive like you have it, because 1<<32 is out of the bits that a cell can hold.

Re: [INFO] Bitsums and Operators

I don't know why it's wron..
I profiled your code here is the result:

Code:

date: Sun Apr 19 19:21:59 2009 map: de_dust

type |                             name |      calls | time / min / max

-------------------------------------------------------------------

   n |                       server_cmd |          1 | 0.000005 / 0.000005 / 0.000005

   p |                       plugin_cfg |          1 | 0.011147 / 0.011147 / 0.011147

   f |                            Index |      20000 | 0.006789 / 0.000000 / 0.000292

   f |                              Bit |      20000 | 0.005406 / 0.000000 / 0.000011

0 natives, 2 public callbacks, 1 function calls were not executed.

Re: [INFO] Bitsums and Operators

Quote:

Originally Posted by Empowers (Post 809456)

I don't know why it's wron..
I profiled your code here is the result:

Code:

date: Sun Apr 19 19:21:59 2009 map: de_dust

type |                             name |      calls | time / min / max

-------------------------------------------------------------------

   n |                       server_cmd |          1 | 0.000005 / 0.000005 / 0.000005

   p |                       plugin_cfg |          1 | 0.011147 / 0.011147 / 0.011147

   f |                            Index |      20000 | 0.006789 / 0.000000 / 0.000292

   f |                              Bit |      20000 | 0.005406 / 0.000000 / 0.000011

0 natives, 2 public callbacks, 1 function calls were not executed.

Your it's wrong because you are doing a continue instead of let the looping run. So you are calling 10 times the command and just giving 10 comparisons.

Re: [INFO] Bitsums and Operators

Anyway it is not that different when it comes to cpu power usage. It helps when we talk about memory usage.