c - What is an intuitive way to interpret the bitwise operators and masking? Also, what is masking used for? -

i'm learning bitwise operators , masking right in computer systems class. i'm having trouble internalizing them.

i understand operators, &, |, ^, >> (both arithmetic , logical shift), , << do, don't quite they're used aside optimizing multiplication , division operations (for >> , <<), , check if bits on or off (the & operator).

also, don't understand masking used for. know doing x & 0xff used extract least significant bit in integer x, can't extrapolate how other kinds of masks (e.g. extract leftmost 1 in number, obtain number of 1s in number, etc.) used?

could please shed light on this, preferably examples? thank you.

a way understand bitmasks example give one. lets have array of structs:

struct my_struct {   int foo;   int bar; };  struct my_struct array_of_structs[64]; // picked 64 specific reason discuss later 

we use array pool , elements of array allocated needed , can deallocated. 1 way accomplish add used boolean member in struct.

struct my_struct {   int foo;   int bar;   char used; }; 

but way create bitmap. since array of size 64, need single 64 bit integer this. note can array of elements bitmap if have more elements bits in single data type omit sake of clarity.

 unsigned long long bitmap;  // guaranteed @ least 64 bits (if recall correctly) 

so lets let every bit correspond element in our array, 0 bit means not used , 1 means used. therefore mark element i used following:

bitmap = bitmap | (1ull << i); 

or more concise:

bitmap |= (1ull << i); 

(1ull << i) has every bit set 0 except ith bit bitmap | (1ull << i) same bitmap except ith bit set (regardless of was). bitmap |= (1ull << i); doing saying want set ith bit 1 , leave else way was. ith bit here used represent whether ith object free or not way interpret want mark ith element used.

now test if element i used or not use &:

if(bitmap & (1ull << i)) {   // used } else {   // not used } 

bitmap & (1ull << i) non-zero value, , therefore true, if ith bit set in bitmap.

finally mark element not used following:

bitmap = bitmap & ~(1ull << i); 

or again more concise

bitmap &= ~(1ull << i); 

~(1ull << i) 64 bits (assuming unsigned long long 64 bits) every bit set 1 except ith bit. when anded bitmap result exact same bitmap except ith bit set 0.

one might wonder when use bitmap vs used variable. in cases bitmap faster although slower , have test works application, if part ever become real bottleneck. 1 example can give of using bitmap mark things used or not used when don't have custom struct. specifically, own experience, use bitmap in operating system mark physical frames used or not used. since there not struct, marking memory itself, bitmap works. however, not efficient in terms of finding free frames works.

another common use mark whether property or attribute present. commonly referred bit flag. example lets have player struct flag element.

struct player {   // members   unsigned long long flag; }; 

we might have various properties player, such jumping, swimming, running, dead. create bitmasks correspond each property.

#define player_jumping  (1ull << 0) #define player_swimming (1ull << 1) #define player_running  (1ull << 2) #define player_dead     (1ull << 3) 

then use similar operations demonstrated toggle properties on , off.

struct player my_player; my_player.flag |= player_jumping; // mark player jumping my_player.flag &= ~player_swimming; // mark player not swimming if(my_player.flag & player_running)  // test if player running 

finally, 1 operation didn't demonstrate before bitwise exclusive or: ^. can use toggle property.

my_player.flag = my_player.flag ^ player_dead; // if player dead player not dead , vise versa 

or again more concise:

my_player.flag ^= player_dead; // if player dead player not dead , vise versa 

this affect specific bit set in bitmask , others left previous value, i.e. x ^ 0 == x @ bit level.

when using bitmasks way can test multiple properties 1 bitwise and. example if care if player running or jumping following:

if(my_player.flag & (player_running | player_jumping))  // test if player running or jumping 

note every compiler convert (player_running | player_jumping) single constant reduces number of operations since 1 member of struct checked opposed two.