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)?

Solution 1

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.

Solution 2

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.

Solution 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/