Bitmasks

[Kalcor]

Can someone kindly explain to me what are bitmasks exactly used for? I read about them on wiki, searched a few topics but my poor brain just can't understand them AT ALL, a friend of mine also stated that a chess game cannot be perfectly done without using bitmasks for the minimax algorithm. It's really hard to understand how they are used exactly :/ can someone help out ?





Also:

Why does this code evaluate: 134217728 when shifting 1 27 bits should evaluate 2097152

#include <iostream>

using namespace std;

int main()
{
    unsigned long quiz1 = 0;


    quiz1 |= 1UL << 27;
//    0000 0000 = 0000 0000 0000 000 00000 0000 0000 0000|
     //           0000 1000 0000 0000 0000 0000 0000 0000
      //          ---------------------------------------
     //           0000 1000 0000 0000 0000 0000 0000 0000
    cout << quiz1 << endl;


    /*quiz1 &= ~(1UL << 27);
    cout << quiz1 << endl;
    bool status = quiz1 & (1UL << 27);
    cout << status;*/
    return 0;
}

[jonnin]

whatever you need, is the general answer.

One example, an old project I worked on, in the TCPIP message format they had designed, the first couple of bytes were bits telling the consumer of the message what pieces were present in the message. So like 00110 would have 2 of the possible 5 body segments in the message.

00001 is 1.
shift it once, its 2, shift it again its 4 ... it doubles every time. So 2 to the power of the number of shifts is the value. You should get 2^27, which is the number you asked about ... its correct, and the number you said it should be is not correct.


The chess game comment is not precisely correct. You can do min/max without it, but bitmasks are faster if done correctly for some algorithms, including this one. Faster means it can look at more moves in the same time, and therefore will pick better moves. If you gave it more time with a different algorithm for the min/max, it would do the same thing, eventually.


I won't try to explain the min/max algorithm here, its on the web in enough places that you should be able to make sense of it with some study of the various explains out there. I can't do any better than what is already written up on it -- but I can say its one of those classic algorithms that are not simple to understand until you look at it for a while -- like the GCD which was invented in BC 800 or something... its short, its simple, but it takes a few to get your head around it.

[Kalcor]

whatever you need, is the general answer.

One example, an old project I worked on, in the TCPIP message format they had designed, the first couple of bytes were bits telling the consumer of the message what pieces were present in the message. So like 00110 would have 2 of the possible 5 body segments in the message.

00001 is 1.
shift it once, its 2, shift it again its 4 ... it doubles every time. So 2 to the power of the number of shifts is the value. You should get 2^27, which is the number you asked about ... its correct, and the number you said it should be is not correct.


The chess game comment is not precisely correct. You can do min/max without it, but bitmasks are faster if done correctly for some algorithms, including this one. Faster means it can look at more moves in the same time, and therefore will pick better moves. If you gave it more time with a different algorithm for the min/max, it would do the same thing, eventually.


I won't try to explain the min/max algorithm here, its on the web in enough places that you should be able to make sense of it with some study of the various explains out there. I can't do any better than what is already written up on it -- but I can say its one of those classic algorithms that are not simple to understand until you look at it for a while -- like the GCD which was invented in BC 800 or something... its short, its simple, but it takes a few to get your head around it.

You said you worked on a project that used bits, can you kindly give an example of how the bits are used you said it in a general way here, and this part:

the first couple of bytes were bits telling the consumer of the message what pieces were present in the message.

This is what I really want to understand, the how to divide the first couple of bytes to do something and the other 2 to do something else and then check on either one of them etc.

And also I don't quite get the 0000 0001 not being the number I said because it shifts this 1 27 times to the left so it promotes this byte to a 4 byte first and then shifts it 27 places, so normally it would be:
0000 0000 0000 0000 0000 0000 0000 0001
shift the one 27 places:
0000 1000 0000 0000 0000 0000 0000 0000

what is wrong about this shift, why shall i use the 2 to the power number of shifts to get the number?

[dhayden]

Why does this code evaluate: 134217728 when shifting 1 27 bits should evaluate 2097152

No, 1 << 22 is 2097152. 1<< 27 is 134217728

[Kalcor]

No, 1 << 22 is 2097152. 1<< 27 is 134217728

Can you represent that in the form of binary? cause that's what's confusing me. Like the one I did earlier:

0000 0000 0000 0000 0000 0000 0000 0001
shift the one 27 places:
0000 1000 0000 0000 0000 0000 0000 0000

Thanks in advance <3

[dhayden]

You're correct. 0000 1000 0000 0000 0000 0000 0000 0000_b = 2²⁷ = 134217728

[JLBorges]

> Can you represent that in the form of binary?

Here's a program that can show the values in binary form:

#include <iostream>
#include <string>
#include <bitset>
#include <limits>
#include <iomanip>

void show_bits( unsigned int value )
{
    static constexpr std::size_t NBITS = std::numeric_limits< unsigned int >::digits ;
    static constexpr std::size_t NDIGITS = std::numeric_limits< unsigned int >::digits10 ;

    std::cout << std::setw(NDIGITS+1) << value << "  " << std::bitset<NBITS>(value) << '\n' ;
}

void shift( unsigned int value, std::size_t by )
{
    show_bits(value) ;

    by %= std::numeric_limits< unsigned int >::digits ;

    std::cout << '\n' << value << "U << " << by << ":\n" ;
    show_bits( value << by ) ;

    std::cout << '\n' << value << "U >> " << by << ":\n" ;
    show_bits( value >> by ) ;

    std::cout << "---------------------------\n" ;
}

int main()
{
    shift( 1, 27 ) ;
    shift( 0b1111000000000000, 12 ) ;
    shift( 0xff, 4 ) ;
}

         1  00000000000000000000000000000001

1U << 27:
 134217728  00001000000000000000000000000000

1U >> 27:
         0  00000000000000000000000000000000
---------------------------
     61440  00000000000000001111000000000000

61440U << 12:
 251658240  00001111000000000000000000000000

61440U >> 12:
        15  00000000000000000000000000001111
---------------------------
       255  00000000000000000000000011111111

255U << 4:
      4080  00000000000000000000111111110000

255U >> 4:
        15  00000000000000000000000000001111

http://coliru.stacked-crooked.com/a/2224bc6b66ff2c5d

[Kalcor]

Thanks everyone :3

[jonnin]

The communications protocol we were using was for vehicles.
say a message could have 5 parts... throttle change, steering change, brake change, all stop emergency, or headlights on/off. I'm totally making that it, its been 15 years, but it was like that.

then each bit represents whether one of those commands exists in the message. If they are not there, you do nothing to that subsystem. And they are parsed in order, so if you have 10101 header the message body will have throttle change message part followed by brake change followed by lights change. Might represent letting of the brake and punching the gas while turning on the lights as a "lets get moving" startup.

there was more to it than this, but that part is true to the format. It saved trying to parse the message in pieces, which at the least would probably mean a full byte for each section saying what it is, instead of 1 byte up front accounting for all of them. The parts were fixed length, I should say that too :)

Mostly we were saving on bandwidth -- we had 1 MB/sec on a good connection and a small fraction of that on a backup connection, and the bare min to function on a very, very slow but very long range connection. So we were cramped on bandwidth at longer ranges or if the strong connection went out (and it would, at times).

That is the common theme with this stuff. In almost all cases bit twiddling stuff is used
- for improved space, usually for transmissions
- for improved speed, as bit ops are very fast most are 1 cpu clock cycle on the chip, so you can do billions of them in a second or so.
- to get those 2 things above, they are often using tricky logic and coding methods, and if not documented, can be quite the challenge to understand. Its a little like one of the best statements in one of the best assembly language books ever written -- by the guys that did doom -- not an exact quote but "it does not matter what the name of the function is. It just matters what it does. That shift routine is also a multiply by 2...."