What are bitwise shift bit-shift operators and how do they work

Question

I ve been attempting to learn C in my spare time  and other languages  C   Java  etc   have the same concept  and often the same operators        What I m wondering is  at a core level  what does bit-shifting   lt  lt    gt  gt    gt  gt  gt   do  what problems can it help solve  and what gotchas lurk around the bend  In other words  an absolute beginner s guide to bit shifting in all its goodness

User · Answer

Bitwise operations  including bit shift  are fundamental to low-level hardware or embedded programming  If you read a specification for a device or even some binary file formats  you will see bytes  words  and dwords  broken up into non-byte aligned bitfields  which contain various values of interest  Accessing these bit-fields for reading writing is the most common usage   A simple real example in graphics programming is that a 16-bit pixel is represented as follows     bit   15  14  13  12  11  10  9   8   7   6   5   4   3   2   1    0                 Blue                  Green                 Red              To get at the green value you would do this     define GREEN MASK  0x7E0   define GREEN OFFSET  5      Read green  uint16 t green    pixel  amp  GREEN MASK   gt  gt  GREEN OFFSET    Explanation  In order to obtain the value of green ONLY  which starts at offset 5 and ends at 10  i e  6-bits long   you need to use a  bit  mask  which when applied against the entire 16-bit pixel  will yield only the bits we are interested in    define GREEN MASK  0x7E0   The appropriate mask is 0x7E0 which in binary is 0000011111100000  which is 2016 in decimal    uint16 t green    pixel  amp  GREEN MASK         To apply a mask  you use the AND operator   amp     uint16 t green    pixel  amp  GREEN MASK   gt  gt  GREEN OFFSET    After applying the mask  you ll end up with a 16-bit number which is really just a 11-bit number since its MSB is in the 11th bit  Green is actually only 6-bits long  so we need to scale it down using a right shift  11 - 6   5   hence the use of 5 as offset   define GREEN OFFSET  5    Also common is using bit shifts for fast multiplication and division by powers of 2    i  lt  lt   x      i    2 x   i  gt  gt   y      i    2 y

User · Answer

Bit Masking  amp  Shifting Bit shifting is often used in low-level graphics programming  For example  a given pixel color value encoded in a 32-bit word   Pixel-Color Value in Hex     B9B9B900  Pixel-Color Value in Binary  10111001  10111001  10111001  00000000  For better understanding  the same binary value labeled with what sections represent what color part                                   Red     Green     Blue       Alpha  Pixel-Color Value in Binary  10111001  10111001  10111001  00000000  Let s say for example we want to get the green value of this pixel s color  We can easily get that value by masking and shifting  Our mask                    Red      Green      Blue      Alpha  color          10111001  10111001  10111001  00000000  green mask     00000000  11111111  00000000  00000000   masked color   color  amp  green mask   masked color   00000000  10111001  00000000  00000000  The logical  amp  operator ensures that only the values where the mask is 1 are kept  The last thing we now have to do  is to get the correct integer value by shifting all those bits to the right by 16 places  logical right shift    green value   masked color  gt  gt  gt  16  Et voil    we have the integer representing the amount of green in the pixel s color   Pixels-Green Value in Hex      000000B9  Pixels-Green Value in Binary   00000000 00000000 00000000 10111001  Pixels-Green Value in Decimal  185  This is often used for encoding or decoding image formats like jpg  png  etc

User · Answer

The Bitwise operators are used to perform operations a bit-level or to manipulate bits in different ways  The bitwise operations are found to be much faster and are some times used to improve the efficiency of a program  Basically  Bitwise operators can be applied to the integer types  long  int  short  char and byte   Bitwise Shift Operators  They are classified into two categories left shift and the right shift    Left Shift  lt  lt     The left shift operator  shifts all of the bits in value to the left a specified number of times  Syntax  value  lt  lt  num  Here num specifies the number of position to left-shift the value in value  That is  the  lt  lt  moves all of the bits in the specified value to the left by the number of bit positions specified by num  For each shift left  the high-order bit is shifted out  and ignored lost   and a zero is brought in on the right  This means that when a left shift is applied to 32-bit compiler  bits are lost once they are shifted past bit position 31  If the compiler is of 64-bit then bits are lost after bit position 63      Output  6   Here the binary representation of 3 is 0   0011 considering 32-bit system  so when it shifted one time the leading zero is ignored lost and all the rest 31 bits shifted to left  And zero is added at the end  So it became 0   0110  the decimal representation of this number is 6    In the case of a negative number      Output  -2  In java negative number  is represented by 2 s complement  SO  -1 represent by 2 32-1 which is equivalent to 1    11 Considering 32-bit system   When shifted one time the leading bit is ignored lost and the rest 31 bits shifted to left and zero is added at the last  So it becomes  11   10 and its decimal equivalent is -2  So  I think you get enough knowledge about the left shift and how its work    Right Shift      The right shift operator  shifts all of the bits in value to the right a specified of times  Syntax  value    num  num specifies the number of positions to right-shift the value in value  That is  the    moves shift all of the bits in the specified value of the right the number of bit positions specified by num  The following code fragment shifts the value 35 to the right by two positions      Output  8  As a binary representation of 35 in a 32-bit system is 00   00100011  so when we right shift it two times the first 30 leading bits are moved shifts to the right side and the two low-order bits are lost ignored and two zeros are added at the leading bits  So  it becomes 00    00001000  the decimal equivalent of this binary representation is 8  Or there is a simple mathematical trick to find out the output of this following code  To generalize this we can say that  x    y   floor x pow 2 y    Consider the above example  x 35 and y 2 so  35 2 2   8 75 and if we take the floor value then the answer is 8     Output     But remember one thing this trick is fine for small values of y if you take the large values of y it gives you incorrect output    In the case of a negative number  Because of the negative numbers the Right shift operator works in two modes signed and unsigned  In signed right shift operator       In case of a positive number  it fills the leading bits with 0  And In case of a negative number  it fills leading bits with 1  To keep the sign  This is called  sign extension        Output  -5  As I explained above the compiler stores the negative value as 2 s complement  So  -10 is represented as 2 32-10 and in binary representation considering 32-bit system 11    0110  When we shift  move one time the first 31 leading bits got shifted in the right side and the low-order bit got lost ignored  So  it becomes 11   0011 and the decimal representation of this number is -5  How I know the sign of number  because the leading bit is 1   It is interesting to note that if you shift -1 right  the result always remains -1 since sign extension keeps bringing in more ones in the high-order bits    Unsigned Right Shift       This operator also shifts bits to the right  The difference between signed and unsigned is the latter fills the leading bits with 1 if the number is negative and the former fills zero in either case  Now the question arises why we need unsigned right operation if we get the desired output by signed right shift operator  Understand this with an example  If you are shifting something that does not represent a numeric value  you may not want sign extension to take place  This situation is common when you are working with pixel-based values and graphics  In these cases  you will generally want to shift a zero into the high-order bit no matter what it s the initial value was      Output  2147483647  Because -2 is represented as 11   10 in a 32-bit system  When we shift the bit by one  the first 31 leading bit is moved shifts in right and the low-order bit is lost ignored and the zero is added to the leading bit  So  it becomes 011   1111  2 31-1  and its decimal equivalent is 2147483647

User · Answer

The bitwise shift operators move the bit values of a binary object  The left operand specifies the value to be shifted  The right operand specifies the number of positions that the bits in the value are to be shifted  The result is not an lvalue  Both operands have the same precedence and are left-to-right associative  Operator     Usage    lt  lt            Indicates the bits are to be shifted to the left     gt  gt            Indicates the bits are to be shifted to the right   Each operand must have an integral or enumeration type  The compiler performs integral promotions on the operands  and then the right operand is converted to type int  The result has the same type as the left operand  after the arithmetic conversions   The right operand should not have a negative value or a value that is greater than or equal to the width in bits of the expression being shifted  The result of bitwise shifts on such values is unpredictable  If the right operand has the value 0  the result is the value of the left operand  after the usual arithmetic conversions   The  lt  lt  operator fills vacated bits with zeros  For example  if left op has the value 4019  the bit pattern  in 16-bit format  of left op is  0000111110110011  The expression left op  lt  lt  3 yields  0111110110011000  The expression left op  gt  gt  3 yields  0000000111110110

User · Answer

The bit shifting operators do exactly what their name implies   They shift bits   Here s a brief  or not-so-brief  introduction to the different shift operators  The Operators   gt  gt  is the  arithmetic  or signed  right shift operator   gt  gt  gt  is the logical  or unsigned  right shift operator   lt  lt  is the left shift operator  and meets the needs of both logical and arithmetic shifts   All of these operators can be applied to integer values  int  long  possibly short and byte or char    In some languages  applying the shift operators to any datatype smaller than int automatically resizes the operand to be an int  Note that  lt  lt  lt  is not an operator  because it would be redundant  Also note that C and C   do not distinguish between the right shift operators   They provide only the  gt  gt  operator  and the right-shifting behavior is implementation defined for signed types   The rest of the answer uses the C    Java operators   In all mainstream C and C   implementations including GCC and Clang LLVM   gt  gt  on signed types is arithmetic   Some code assumes this  but it isn t something the standard guarantees   It s not undefined  though  the standard requires implementations to define it one way or another   However  left shifts of negative signed numbers is undefined behaviour  signed integer overflow    So unless you need arithmetic right shift  it s usually a good idea to do your bit-shifting with unsigned types    Left shift   lt  lt   Integers are stored  in memory  as a series of bits   For example  the number 6 stored as a 32-bit int would be  00000000 00000000 00000000 00000110  Shifting this bit pattern to the left one position  6  lt  lt  1  would result in the number 12  00000000 00000000 00000000 00001100  As you can see  the digits have shifted to the left by one position  and the last digit on the right is filled with a zero   You might also note that shifting left is equivalent to multiplication by powers of 2   So 6  lt  lt  1 is equivalent to 6   2  and 6  lt  lt  3 is equivalent to 6   8   A good optimizing compiler will replace multiplications with shifts when possible  Non-circular shifting Please note that these are not circular shifts   Shifting this value to the left by one position  3 758 096 384  lt  lt  1   11100000 00000000 00000000 00000000  results in 3 221 225 472  11000000 00000000 00000000 00000000  The digit that gets shifted  quot off the end quot  is lost   It does not wrap around   Logical right shift   gt  gt  gt   A logical right shift is the converse to the left shift   Rather than moving bits to the left  they simply move to the right   For example  shifting the number 12  00000000 00000000 00000000 00001100  to the right by one position  12  gt  gt  gt  1  will get back our original 6  00000000 00000000 00000000 00000110  So we see that shifting to the right is equivalent to division by powers of 2  Lost bits are gone However  a shift cannot reclaim  quot lost quot  bits   For example  if we shift this pattern  00111000 00000000 00000000 00000110  to the left 4 positions  939 524 102  lt  lt  4   we get 2 147 483 744  10000000 00000000 00000000 01100000  and then shifting back   939 524 102  lt  lt  4   gt  gt  gt  4  we get 134 217 734  00001000 00000000 00000000 00000110  We cannot get back our original value once we have lost bits   Arithmetic right shift   gt  gt   The arithmetic right shift is exactly like the logical right shift  except instead of padding with zero  it pads with the most significant bit   This is because the most significant bit is the sign bit  or the bit that distinguishes positive and negative numbers   By padding with the most significant bit  the arithmetic right shift is sign-preserving  For example  if we interpret this bit pattern as a negative number  10000000 00000000 00000000 01100000  we have the number -2 147 483 552   Shifting this to the right 4 positions with the arithmetic shift  -2 147 483 552  gt  gt  4  would give us  11111000 00000000 00000000 00000110  or the number -134 217 722  So we see that we have preserved the sign of our negative numbers by using the arithmetic right shift  rather than the logical right shift   And once again  we see that we are performing division by powers of 2

User · Answer

Be aware of that only 32 bit version of PHP is available on the Windows platform   Then if you for instance shift  lt  lt  or    more than by 31 bits  results are unexpectable  Usually the original number instead of zeros will be returned  and it can be a really tricky bug   Of course if you use 64 bit version of PHP  Unix   you should avoid shifting by more than 63 bits  However  for instance  MySQL uses the 64-bit BIGINT  so there should not be any compatibility problems   UPDATE  From PHP 7 Windows  PHP builds are finally able to use full 64 bit integers  The size of an integer is platform-dependent  although a maximum value of about two billion is the usual value  that s 32 bits signed   64-bit platforms usually have a maximum value of about 9E18  except on Windows prior to PHP 7  where it was always 32 bit

User · Answer

Note that in the Java implementation  the number of bits to shift is mod d by the size of the source   For example    long  4  gt  gt  65   equals 2   You might expect shifting the bits to the right 65 times would zero everything out  but it s actually the equivalent of    long  4  gt  gt   65   64    This is true for  lt  lt       and       I have not tried it out in other languages

User · Answer

I am writing tips and tricks only  It may be useful in tests and exams     n   n 2  n   n lt  lt 1 n   n 2  n   n gt  gt 1 Checking if n is power of 2  1 2 4 8       check   n  amp   n-1   Getting xth bit of n  n     1  lt  lt  x  Checking if x is even or odd  x amp 1    0  even  Toggle the nth bit of x  x    1 lt  lt n

User · Answer

Some useful bit operations manipulations in Python   I implemented Ravi Prakash s answer in Python     Basic bit operations   Integer to binary print bin 10      Binary to integer print int  1010   2      Multiplying x with 2      x  2    x  lt  lt  1 print 200  lt  lt  1     Dividing x with 2      x 2    x  gt  gt  1 print 200  gt  gt  1     Modulo x with 2      x   2    x  amp  1 if 20  amp  1    0      print  20 is a even number      Check if n is power of 2  check   n  amp   n-1   print not 33  amp   33-1       Getting xth bit of n   n  gt  gt  x   amp  1 print  10  gt  gt  2   amp  1    Bin of 10    1010 and second bit is 0    Toggle nth bit of x   x  1  lt  lt  n    take bin 10     1010 and toggling second bit in bin 10  we get 1110     bin 14  print 10  1  lt  lt  2

User · Answer

Let s say we have a single byte   0110110   Applying a single left bitshift gets us   1101100   The leftmost zero was shifted out of the byte  and a new zero was appended to the right end of the byte   The bits don t rollover  they are discarded  That means if you left shift 1101100 and then right shift it  you won t get the same result back   Shifting left by N is equivalent to multiplying by 2N   Shifting right by N is  if you are using ones  complement  is the equivalent of dividing by 2N and rounding to zero   Bitshifting can be used for insanely fast multiplication and division  provided you are working with a power of 2  Almost all low-level graphics routines use bitshifting   For example  way back in the olden days  we used mode 13h  320x200 256 colors  for games  In Mode 13h  the video memory was laid out sequentially per pixel  That meant to calculate the location for a pixel  you would use the following math   memoryOffset    row   320    column   Now  back in that day and age  speed was critical  so we would use bitshifts to do this operation   However  320 is not a power of two  so to get around this we have to find out what is a power of two that added together makes 320    row   320     row   256     row   64    Now we can convert that into left shifts    row   320     row  lt  lt  8     row  lt  lt  6    For a final result of   memoryOffset     row  lt  lt  8     row  lt  lt  6     column   Now we get the same offset as before  except instead of an expensive multiplication operation  we use the two bitshifts   in x86 it would be something like this  note  it s been forever since I ve done assembly  editor s note  corrected a couple mistakes and added a 32-bit example     mov ax  320  2 cycles mul word  row   22 CPU Cycles mov di ax  2 cycles add di   column   2 cycles   di    row  320    column     16-bit addressing mode limitations     di  is a valid addressing mode  but  ax  isn t  otherwise we could skip the last mov   Total  28 cycles on whatever ancient CPU had these timings   Vrs  mov ax   row   2 cycles mov di  ax  2 shl ax  6   2 shl di  8   2 add di  ax  2     320   256 64  add di   column   2   di    row   256 64     column    12 cycles on the same ancient CPU   Yes  we would work this hard to shave off 16 CPU cycles   In 32 or 64-bit mode  both versions get a lot shorter and faster   Modern out-of-order execution CPUs like Intel Skylake  see http   agner org optimize   have very fast hardware multiply  low latency and high throughput   so the gain is much smaller   AMD Bulldozer-family is a bit slower  especially for 64-bit multiply   On Intel CPUs  and AMD Ryzen  two shifts are slightly lower latency but more instructions than a multiply  which may lead to lower throughput    imul edi   row   320      3 cycle latency from  row  being ready add  edi   column         1 cycle latency  from  column  and edi being ready     edi    row   256 64     column    in 4 cycles from  row  being ready    vs   mov edi   row  shl edi  6                 row 64    1 cycle latency lea edi   edi   edi 4      row  64   64 4    1 cycle latency add edi   column           1 cycle latency from edi and  column  both being ready   edi    row   256 64     column    in 3 cycles from  row  being ready    Compilers will do this for you  See how GCC  Clang  and Microsoft Visual C   all use shift lea when optimizing return 320 row   col    The most interesting thing to note here is that x86 has a shift-and-add instruction  LEA  that can do small left shifts and add at the same time  with the performance as an add instruction   ARM is even more powerful  one operand of any instruction can be left or right shifted for free   So scaling by a compile-time-constant that s known to be a power-of-2 can be even more efficient than a multiply     OK  back in the modern days    something more useful now would be to use bitshifting to store two 8-bit values in a 16-bit integer  For example  in C       Byte1  11110000    Byte2  00001111  Int16 value     byte  Byte1  gt  gt  8    Byte2        value   000011111110000    In C    compilers should do this for you if you used a struct with two 8-bit members  but in practice they don t always

User · Answer

One gotcha is that the following is implementation dependent  according to the ANSI standard     char x   -1  x  gt  gt  1    x can now be 127  01111111  or still -1  11111111    In practice  it s usually the latter

[language-agnostic] What are bitwise shift (bit-shift) operators and how do they work?

Examples related to language-agnostic

Examples related to bit-manipulation

Examples related to operators

Examples related to bit-shift

Examples related to binary-operators