Multiplication and division can be achieved using bit operators, for example

    i*2 = i&lt;&lt;1
    i*3 = (i&lt;&lt;1) + i;
    i*10 = (i&lt;&lt;3) + (i&lt;&lt;1)

and so on.

Is it actually faster to use say `(i&lt;&lt;3)+(i&lt;&lt;1)` to multiply with 10 than using `i*10` directly? Is there any sort of input that can&#39;t be multiplied or divided in this way?


Is multiplication and division using shift operators in C actually faster?

Given by a colleague as a puzzle, I cannot figure out how this C program actually compiles and runs. What is this `&gt;&gt;&gt;=` operator and the strange `1P1` literal? I have tested in Clang and GCC. There are no warnings and the output is &quot;???&quot;

    #include &lt;stdio.h&gt;

    int main()
    {
        int a[2]={ 10, 1 };
	
        while( a[ 0xFULL?&#39;\0&#39;:-1:&gt;&gt;&gt;=a&lt;:!!0X.1P1 ] )
            printf(&quot;?&quot;);
	
	    return 0;
    }

What is the &gt;&gt;&gt;= operator in C?

In the following code:

    short = ((byte2 &lt;&lt; 8) | (byte1 &amp; 0xFF))

What is the purpose of `&amp;0xFF`?
Because other somestimes I see it written as:

    short = ((byte2 &lt;&lt; 8) | byte1)

And that seems to work fine too?

What does AND 0xFF do?

In C bitwise left shift operation invokes Undefined Behaviour when the left side operand has negative value.

Relevant quote from ISO C99 (6.5.7/4)

&gt; The  result  of E1 &lt;&lt; E2 is E1 left-shifted E2 bit  positions;  vacated  bits  are  ﬁlled  with zeros.  If E1 has an unsigned type, the value of the result is E1 &#215; 2&lt;sup&gt;E2&lt;/sup&gt;, reduced modulo
one more than the maximum value representable in the result type.  If E1 has a signed
type and nonnegative value, and E1 &#215; 2&lt;sup&gt;E2&lt;/sup&gt; is representable in the result type, then that is
the resulting value; otherwise, **the behavior is undeﬁned**.

But in C++ the behaviour is well defined.

ISO C++-03 (5.8/2)

&gt;The value of E1 &lt;&lt; E2 is E1 (interpreted as a bit pattern) left-shifted E2 bit positions; vacated bits are zero-filled.  If E1 has an unsigned type, the value of the result is E1 multiplied by the quantity 2 raised to the power E2, reduced modulo ULONG_MAX+1 if E1 has type unsigned long, UINT_MAX+1 otherwise.
[Note: the constants ULONG_MAXand UINT_MAXare defined in the header &lt;climits&gt;).  ]

That means

    int a = -1, b=2, c;
    c= a &lt;&lt; b ;

invokes Undefined Behaviour in C but the behaviour is well defined in C++.

What forced the ISO C++ committee to consider that behaviour well defined as opposed to the behaviour in C?

On the other hand the behaviour is `implementation defined` for bitwise right shift operation when the left operand is negative, right?

My question is why does left shift operation invoke Undefined Behaviour in C and why does right shift operator invoke just Implementation defined behaviour?

P.S : Please don&#39;t give answers like &quot;It is undefined behaviour because the Standard says so&quot;. :P






Why does left shift operation invoke Undefined Behaviour when the left side operand has negative value?

I discovered this oddity:

    for (long l = 4946144450195624l; l &gt; 0; l &gt;&gt;= 5)
        System.out.print((char) (((l &amp; 31 | 64) % 95) + 32));

Output:

    hello world

How does this work?

How does this print &quot;hello world&quot;?

I was looking at code from Mozilla that add a filter method to Array and it had a line of code that confused me.
 
    var len = this.length &gt;&gt;&gt; 0;

I have never seen &gt;&gt;&gt; used in JavaScript before. &lt;br&gt;What is it and what does it do?


What is the JavaScript &gt;&gt;&gt; operator and how do you use it?

In C, are the shift operators (`&lt;&lt;`, `&gt;&gt;`) arithmetic or logical?

Are the shift operators (&lt;&lt;, &gt;&gt;) arithmetic or logical in C?

I was looking at the source of [sorted_containers][1] and was surprised to see [this line](https://github.com/grantjenks/sorted_containers/blob/master/sortedcontainers/sortedlist.py#L72):

    self._load, self._twice, self._half = load, load * 2, load &gt;&gt; 1

Here `load` is an integer. Why use bit shift in one place, and multiplication in another? It seems reasonable that bit shifting may be faster than integral division by 2, but why not replace the multiplication by a shift as well? I benchmarked the the following cases:

 1. (times, divide)
 1. (shift, shift)
 1. (times, shift)
 1. (shift, divide)

and found that #3 is consistently faster than other alternatives:

    # self._load, self._twice, self._half = load, load * 2, load &gt;&gt; 1
    
    import random
    import timeit
    import pandas as pd
    
    x = random.randint(10 ** 3, 10 ** 6)
    
    def test_naive():
        a, b, c = x, 2 * x, x // 2
        
    def test_shift():
        a, b, c = x, x &lt;&lt; 1, x &gt;&gt; 1    
    
    def test_mixed():
        a, b, c = x, x * 2, x &gt;&gt; 1    
    
    def test_mixed_swapped():
        a, b, c = x, x &lt;&lt; 1, x // 2
        
    def observe(k):
        print(k)
        return {
            &#39;naive&#39;: timeit.timeit(test_naive),
            &#39;shift&#39;: timeit.timeit(test_shift),
            &#39;mixed&#39;: timeit.timeit(test_mixed),
            &#39;mixed_swapped&#39;: timeit.timeit(test_mixed_swapped),
        }
        
    def get_observations():
        return pd.DataFrame([observe(k) for k in range(100)])

[![enter image description here][2]][2]
[![enter image description here][3]][3]

The question:

Is my test valid? If so, why is (multiply, shift) faster than (shift, shift)?

I run Python 3.5 on Ubuntu 14.04.

**Edit**

Above is the original statement of the question. Dan Getz provides an excellent explanation in his answer.

For the sake of completeness, here are sample illustrations for larger `x` when multiplication optimizations do not apply.

[![enter image description here][4]][4]
[![enter image description here][5]][5]


  [1]: https://github.com/grantjenks/sorted_containers/blob/master/sortedcontainers/sortedlist.py
  [2]: http://i.stack.imgur.com/mrSuI.png
  [3]: http://i.stack.imgur.com/Yo4wL.png
  [4]: http://i.stack.imgur.com/2btSH.png
  [5]: http://i.stack.imgur.com/ItTVG.png

Times-two faster than bit-shift, for Python 3.x integers?

I am trying to understand the shift operators and couldn&#39;t get much.
When I tried to execute the below code

    System.out.println(Integer.toBinaryString(2 &lt;&lt; 11));
    System.out.println(Integer.toBinaryString(2 &lt;&lt; 22));
    System.out.println(Integer.toBinaryString(2 &lt;&lt; 33));
    System.out.println(Integer.toBinaryString(2 &lt;&lt; 44));
    System.out.println(Integer.toBinaryString(2 &lt;&lt; 55));

I get the below

    1000000000000    
    100000000000000000000000    
    100    
    10000000000000    
    1000000000000000000000000    

Could somebody please explain?


How do shift operators work in Java?

Have you ever had to use [bit shifting][1] in real programming projects? Most (if not all) high level languages have shift operators in them, but when would you actually need to use them?


  [1]: http://en.wikipedia.org/wiki/Bit_shift#Bit_shifts

Have you ever had to use bit shifting in real projects?

Does [endianness][1] matter at all with the bitwise operations? Either [logical][2] or shifting? 

I&#39;m working on homework with regard to bitwise operators, and I can not make heads or tails on it, and I think I&#39;m getting quite hung up on the endianess. That is, I&#39;m using a little endian machine (like most are), but does this need to be considered or is it a wasted fact? 

In case it matters, I&#39;m using C.

  [1]: http://en.wikipedia.org/wiki/Endianness
  [2]: https://stackoverflow.com/questions/1036141/bitwise-not-operator-in-c-with-regards-to-little-endian-and-big-endian


Bitwise operators and &quot;endianness&quot;

What method would you use to determine if the the bit that represents 2^x is a 1 or 0 ?

Java: Checking if a bit is 0 or 1 in a long

When I write the following program and use the GNU C++ compiler, the output is `1` which I think is due to the rotation operation performed by the compiler.

    #include &lt;iostream&gt;
    
    int main()
    {
        int a = 1;
        std::cout &lt;&lt; (a &lt;&lt; 32) &lt;&lt; std::endl;
        
        return 0;
    }

But logically, as it&#39;s said that the bits are lost if they overflow the bit width, the output should be 0. What is happening?

The code is on ideone, http://ideone.com/VPTwj.


Why doesn&#39;t left bit-shift, &quot;&lt;&lt;&quot;, for 32-bit integers work as expected when used more than 32 times?

I&#39;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&#39;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&#39;s guide to bit shifting in all its goodness.



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

I&#39;m very new to dealing with bits and have got stuck on the following warning when compiling:

&gt;      7: warning: left shift count &gt;= width of type

My line 7 looks like this

    unsigned long int x = 1 &lt;&lt; 32;

This would make sense if the size of `long` on my system was 32 bits. However, `sizeof(long)` returns `8` and `CHAR_BIT` is defined as `8` suggesting that long should be 8x8 = 64 bits long.

What am I missing here? Are `sizeof` and `CHAR_BIT` inaccurate or have I misunderstood something fundamental?

warning: left shift count &gt;= width of type

I am trying to figure out how exactly arithmetic bit-shift operators work in C, and how it will affect signed 32-bit integers.

To make things simple, let&#39;s say we work within one byte (8 bits):

    x = 1101.0101
    MSB[ 1101.0101 ]LSB

Reading other posts on Stack Overflow and some websites, I found that:
`&lt;&lt;` will shift toward MSB (to the left, in my case), and fill &quot;empty&quot; LSB bits with 0s.

And `&gt;&gt;` will shift toward LSB (to the right, in my case) and fill &quot;empty&quot; bits with MS bit

So, `x = x &lt;&lt; 7` will result in moving LSB to MSB, and setting everything to 0s.

    1000.0000

Now, let&#39;s say I would `&gt;&gt; 7`, last result. This would result in `[0000.0010]`? Am I right?

Am I right about my assumptions about shift operators?

I just tested on my machine, **

    int x = 1;   //000000000......01

    x = x &lt;&lt; 31; //100000000......00

    x = x &gt;&gt; 31; //111111111......11 (Everything is filled with 1s !!!!!) 

Why?


Arithmetic bit-shift on a signed integer

I&#39;ve seen the operators `&gt;&gt;` and `&lt;&lt;` in various code that I&#39;ve looked at (none of which I actually understood), but I&#39;m just wondering what they actually do and what some practical uses of them are.

If the shifts are like `x * 2` and `x / 2`, what is the real difference from actually using the `*` and `/` operators? Is there a performance difference?


What does a bitwise shift (left or right) do and what is it used for?

I am trying to do assignment: &quot;Find the number of bits in an unsigned integer data type without using the sizeof() function.&quot;

And my design is to convert the integer to bits and then to count them. For ex: `10 is 1010` and `5 is 101`

[Converting integer to a bit representation][1] shows something like this:

    do
    { 
        Vec.push_back( x &amp; 1 ) 
    } 
    while ( x &gt;&gt;= 1 );

I don&#39;t want to just copy paste stuff. When I use F-10 I see what `(x &amp; 1)` is doing but I don&#39;t know it is name or how it does its job(compare something?). Also I know `&gt;=` which &quot;greater than or equal&quot; but what is `x &gt;&gt;= 1`?

Note: The marked duplicate is a JavaScript and not C++

  [1]: https://stackoverflow.com/questions/2686542/converting-integer-to-a-bit-representation

All Bit Shift Solutions on Gang of Coders

Total of 18 Bit Shift Solutions

Is multiplication and division using shift operators in C actually faster?

What is the >>>= operator in C?

What does AND 0xFF do?

Why does left shift operation invoke Undefined Behaviour when the left side operand has negative value?

How does this print "hello world"?

What is the JavaScript >>> operator and how do you use it?

Are the shift operators (<<, >>) arithmetic or logical in C?

Times-two faster than bit-shift, for Python 3.x integers?

How do shift operators work in Java?

Have you ever had to use bit shifting in real projects?

Bitwise operators and "endianness"

Java: Checking if a bit is 0 or 1 in a long

Why doesn't left bit-shift, "<<", for 32-bit integers work as expected when used more than 32 times?

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

warning: left shift count >= width of type

Arithmetic bit-shift on a signed integer

What does a bitwise shift (left or right) do and what is it used for?

What is (x & 1) and (x >>= 1)?