Decimal Division by left shift

Question

I have been given a question to convert base from 10 to 2 without using division(/) and modulus(%), so I came up with solution of using bitwise AND(&) and right shift(>>) operators.

So I start to learn what these two operators exactly do but still for some questions I could not find answer or understand the logic behind.

If I understand correctly division works according the digits place value, in decimal and binary both. When we divide the number by 10 or 2 ,we shift the place value by one place to right in both, which this will result in division by 10 in decimal and by two in binary.

X=120 (in base of ten) if X>>1 we will have X=12 (division by 10)

Y=1000 (in base of two) if Y>>1 we will have X=100 (division by 2)

but when I use this piece of code:

#include<iostream>
using namespace std ;

int main()
{
    int a,b=1;
    cout <<"enter an integer"<<endl;
    cin>> a;
    cout<<(a & b)<<endl;
    a=a>>1;
    cout<<a;
    cout<<endl;
    system("pause");
    return 0 ;
}

I get comfused cause in my mind it was like this

a=120 (in base of ten) if X>>1 we will have X=12 (division by 10)

but the result was this

a=120 (in base of ten) if X>>1 we have X=60 (division by 2!!)

I do not understand two main points about the result:

First, if this operator(>>) just shift the place value of the digits in code and don't change the base of the number(10) it should produce another result(12) than we can see in result of code (which it is 60). Why we can see this result(60) but not 12?

Second, if it does binary left shift (which it seems like this for me), does it change the decimal to binary at first by IDE or not?

And about the bitwise AND if it is logical gate(which it seems it is) :

1.How can we put other values except 0 and 1 and still have an answer?

2.According Bitwise AND rules

Y&1=Y

Then it should be 120 but the result of code is 1. What is explanation for this?

3.How it can generate the remainder (according which mathematical operations and logic)?

Answer 1

The >> operator in C++ always does binary shifting, never decimal shifting. There is no decimal shifting operator. You're welcome to write your own function that does that, if you want one.

Although it's not wrong to think of mathematical division by 10 as a shift by one decimal place, that's not how C++ does shifting. Also, it's shifting to the right, not the left — look which way the brackets are pointing.

You've also misunderstood bitwise definitions. It's true that Y & 1 = Y, when Y is a bit. When Y is more than just one bit, the definition is extended to apply the one-bit definition to each bit in the two operands. That's what bitwise means. The operator is applied bitwise to the operands: The first bit of the left operand is combined with the first bit of the right operand to yield the first bit of the result. Likewise, the second bits of each of the two operands determine the second bit of the result, and so on for each pair of bits in the operands.

To calculate the remainder from dividing two numbers, use the % operator, also known as the modulo operator. Read more about it in your C++ textbook.

Answer 2

The shift operators in C++ always use base 2. That is, x >> 1 shifts the value x by one binary digits. Note, however, that it isn't a good idea to shift signed integers as their value gets easily unspecified: When playing with bit logic, you always want to use unsigned integers, e.g., unsigned int or unsigned long. The conversion from your decimal values to the internal representation is done by the input operation which, BTW, needs to be checked for success:

if (std::cin >> a) {
     ...
}
else {
    std::cerr << "ERROR: failed to read value a\n";
}

The other binary operation (& for and, | for or, ^ for _xor, and ~ for invert) operate on the individual bits. For example, 7u & 13u yields 5u. To get the remainder of a division by a power of 2 you just use and prior to the division with a suitable bitmask.

BTW, if you want to get a better feel of how these guys work in binary, you might want to play with std::bitset<8>: this class template has the same bitwise operations, can be constructed from an integer, and when printed shows the individual bits.

Answer 3

The << and >> operators are bitwise operators, which "operate" in base 2.

http://en.wikipedia.org/wiki/Bitwise_operation#Shifts_in_C.2C_C.2B.2B.2C_C.23

http://www.cplusplus.com/doc/tutorial/operators/

Answer 4

With bitwise shifting you are working in binary, not decimal.

In memory, 120 is stored in binary which = 1111000 shifted right 1 = 111100 or 60

http://www.binaryhexconverter.com/binary-to-decimal-converter

Demonstrates shifting: http://www.miniwebtool.com/bitwise-calculator/bit-shift/

Answer 5

When you read the input by cin >> a there is a conversion of the character string "120" to the integer 120. In memory and the CPU the integer is (probably, depending on your system) represented as the 32 bits 00000000 00000000 00000000 01111000. If you are using windows a convenient way to see the bit-pattern of a number is the windows calculator in programmer mode.

The & operation operates bit-wise. In the CPU there are 32 and-gates which compute the result on each bit position:

a     = 00000000 00000000 00000000 01111000
b     = 00000000 00000000 00000000 00000001
a & b = 00000000 00000000 00000000 00000000

So the result is the integer 0 and not 1 as you have written.

Another example with b=231: The result is 96, only the bits at positions 5 and 6 are set, for all other positions at least one input bit is 0.

a     = 00000000 00000000 00000000 01111000
b     = 00000000 00000000 00000000 11100111
a & b = 00000000 00000000 00000000 01100000

after a = a>>1 all bits are shifted one position to the right. what happens on the leftmost bit is depending on the sign, so as Dietmar recommends it is preferrable to use unsigned datatypes for bit manipulations.

a = 00000000 00000000 00000000 00111100

When you print the result with cout << a, this bit pattern is converted back to a decimal representation as the character string "60".