What do two left-angle brackets "<<" mean in C#?
When you write
1 << n
You shift the bit combination 000000001
for n
times left and thus put n
into the exponent of 2:
2^n
So
1 << 10
Really is
1024
For a list of say 5 items your for
will cycle 32 times.
It is called left-shift
operator. Take a look at the documentation
The left-shift operator causes the bit pattern in the first operand to be shifted to the left by the number of bits specified by the second operand. Bits vacated by the shift operation are zero-filled. This is a logical shift instead of a shift-and-rotate operation.
Simple example that demonstrates the left-shift
operator:
for (int i = 0; i < 10; i++)
{
var shiftedValue = 1 << i;
Console.WriteLine(" 1 << {0} = {1} \t Binary: {2}",i,shiftedValue,Convert.ToString(shiftedValue,2).PadLeft(10,'0'));
}
//Output:
// 1 << 0 = 1 Binary: 0000000001
// 1 << 1 = 2 Binary: 0000000010
// 1 << 2 = 4 Binary: 0000000100
// 1 << 3 = 8 Binary: 0000001000
// 1 << 4 = 16 Binary: 0000010000
// 1 << 5 = 32 Binary: 0000100000
// 1 << 6 = 64 Binary: 0001000000
// 1 << 7 = 128 Binary: 0010000000
// 1 << 8 = 256 Binary: 0100000000
// 1 << 9 = 512 Binary: 1000000000
Moving one bit to left is equivelant to multiple by two.In fact,moving bits are faster than standart multiplication.Let's take a look at an example that demonstrates this fact:
Let's say we have two methods:
static void ShiftBits(long number,int count)
{
long value = number;
for (int i = 0; i < count; i+=128)
{
for (int j = 1; j < 65; j++)
{
value = value << j;
}
for (int j = 1; j < 65; j++)
{
value = value >> j;
}
}
}
static void MultipleAndDivide(long number, int count)
{
long value = number;
for (int i = 0; i < count; i += 128)
{
for (int j = 1; j < 65; j++)
{
value = value * (2 * j);
}
for (int j = 1; j < 65; j++)
{
value = value / (2 * j);
}
}
}
And we want to test them like this:
ShiftBits(1, 10000000);
ShiftBits(1, 100000000);
ShiftBits(1, 1000000000);
...
MultipleAndDivide(1, 10000000);
MultipleAndDivide(1, 100000000);
MultipleAndDivide(1, 1000000000);
...
Here is the results:
Bit manipulation 10.000.000 times: 58 milliseconds
Bit manipulation 100.000.000 times: 375 milliseconds
Bit manipulation 1.000.000.000 times: 4073 milliseconds
Multiplication and Division 10.000.000 times: 81 milliseconds
Multiplication and Division 100.000.000 times: 824 milliseconds
Multiplication and Division 1.000.000.000 times: 8224 milliseconds