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

Question

I am trying to do assignment: "Find the number of bits in an unsigned integer data type without using the sizeof() function."

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 shows something like this:

do
{ 
    Vec.push_back( x & 1 ) 
} 
while ( x >>= 1 );

I don't want to just copy paste stuff. When I use F-10 I see what (x & 1) is doing but I don't know it is name or how it does its job(compare something?). Also I know >= which "greater than or equal" but what is x >>= 1?

Note: The marked duplicate is a JavaScript and not C++

Doggy

I don't understand all the downvotes. &, >>=, and other operators are notoriously hard to search on the internet. The question is simple for someone who has seen these operators before, but they are not self-explanatory, and could be quite overwhelming when you see them for the first time. – Cervine

Good title. Very clear question. Aswerable fairly easy with a text book but with difficulty using online resources. Maybe not upvote-worthy, but certainly not deserving of the torpedo bombing it received. – Supersensitive

Strongly recommend getting a good book, but if this is not possible, a good starter can be found here.. Excellent technical documentation can be found here, often with examples. – Supersensitive

@Supersensitive Thank you for the references I looked at all of them :) – Doggy

Possible duplicate of What does operator >>= mean – Deserted

Caution: while your approach may be doing something similar to what your instructor really wants, the problem as stated - "Find the number of bits in an unsigned integer data type without using the sizeof() function" - is about finding the size of a data type not a value. I think you can ensure all bits are set to 1 by assigning a value of -1 (which will be converted to the maximum possible unsigned integer when assigned) and then counting the bits in that value. – Sejant

@RaymondChen: really bad idea to teach people to look at Javascript documentation to learn about C++ operators. – Rubie

Question is unclear to me: the title asks for the number of bits in an integer, and the mention of sizeof suggests that sizeof x * CHAR_BIT would give the right answer. But the code in the question only measures the count of significant bits in a particular argument (i.e. not counting zero-bits before the first 1-bit). These are different things. – Nelson

Instead of -1 you probably ought to use ~0U to set all the bits to 1. – Berlin

Possible duplicate of What are bitwise operators? – Pycnometer

Answer 1

These are Bitwise Operators (reference).

x & 1 produces a value that is either 1 or 0, depending on the least significant bit of x: if the last bit is 1, the result of x & 1 is 1; otherwise, it is 0. This is a bitwise AND operation.

x >>= 1 means "set x to itself shifted by one bit to the right". The expression evaluates to the new value of x after the shift.

Note: The value of the most significant bit after the shift is zero for values of unsigned type. For values of signed type the most significant bit is copied from the sign bit of the value prior to shifting as part of sign extension, so the loop will never finish if x is a signed type, and the initial value is negative.

Cervine

Hi and thanks. Could you please explain more on (depending on the last bit) and (shifted by one to the right)? – Doggy

I suspect @MaximEgorushkin might be hinting that it is implementation-defined whether right shifts of negative numbers bring in a zero or a one in the top bit. – Bravado

x >>= 1 expression means 1) shift the value of x 1 bit right, 2) assign the new value to x and 3) return the new value of x as the value of the expression. Without 3 that while condition would be meaningless. – Luciano

@MaximEgorushkin That's a fair point - the compound assignment is used as an expression, not as a statement, so knowing what's the value of the expression is important. Thanks! – Cervine

@KenY-N Thanks for the comment. This is a fair observation, because making x signed and starting it with a negative will make an infinite loop. – Cervine

Nit: x & 1 may not have type int depending on the type of x. In particular, if x is long, then x&1 will be long. – Skyscraper

" For values of signed type the most significant bit is copied from the value prior to shifting," - not necessarily. – Skyscraper

Answer 2

x & 1 is equivalent to x % 2.

x >> 1 is equivalent to x / 2

So, these things are basically the result and remainder of divide by two.

Dzerzhinsk

This is true, for signed numbers, in two's compliment only. For unsigned numbers it is accurate. – Embodiment

What about if its x | 1 and x<<1 ? Just eager to know. – Stapler

@SafinGhoghabori till 0x3fffffff; 1073741823 x<<1 is x*2 after that value it gives negative values as the MSB becomes 1. x | 1 gives the same value if x is odd, else x+1. – Caputto

Answer 3

In addition to the answer of "dasblinkenlight" I think an example could help. I will only use 8 bits for a better understanding.

x & 1 produces a value that is either 1 or 0, depending on the least significant bit of x: if the last bit is 1, the result of x & 1 is 1; otherwise, it is 0. This is a bitwise AND operation.

This is because 1 will be represented in bits as 00000001. Only the last bit is set to 1. Let's assume x is 185 which will be represented in bits as 10111001. If you apply a bitwise AND operation on x with 1 this will be the result:

00000001
10111001
--------
00000001

The first seven bits of the operation result will be 0 after the operation and will carry no information in this case (see Logical AND operation). Because whatever the first seven bits of the operand x were before, after the operation they will be 0. But the last bit of the operand 1 is 1 and it will reveal if the last bit of operand x was 0 or 1. So in this example the result of the bitwise AND operation will be 1 because our last bit of x is 1. If the last bit would have been 0, then the result would have been also 0, indicating that the last bit of operand x is 0:

00000001
10111000
--------
00000000

x >>= 1 means "set x to itself shifted by one bit to the right". The expression evaluates to the new value of x after the shift

Let's pick the example from above. For x >>= 1 this would be:

10111001
--------
01011100

And for left shift x <<= 1 it would be:

10111001
--------
01110010

Please pay attention to the note of user "dasblinkenlight" in regard to shifts.

Fluidextract

Great explanation. Thanks! Could you show a basic realistic problem that could be solved by these operators? Other than the example in OP? Please and thanks again – Doggy

E.g. you could use both operators for reversing the bits of an Integer. See the first example of: Reverse Bits of Integer. In the first example both operators will be used. And the shift operators are very handy for multiplication and divisions by 2: Use the shift operators to multiply and divide by 2 – Fluidextract

Answer 4

It is similar to x = (x >> 1).

(operand1)(operator)=(operand2)  implies(=>)  (operand1)=(operand1)(operator)(operand2) 

It shifts the binary value of x by one to the right.

E.g.

int x=3;    // binary form (011) 
x = x >> 1; // zero shifted in from the left, 1 shifted out to the right:
            // x=1, binary form (001)

Atc

Answer 5

(n & 1) will check if 'n' is odd or even, this is similar to (n%2).

1. In case 'n' is odd (n & 1) will return true/1;

2. Else it will return back false/0;

---

The '>>' in (n>>=1) is a bitwise operator called "Right shift", this operator will modify the value of 'n', the formula is:

(n >>= m) => (n = n>>m) => (n = n/2^m)

Go through GeeksforGeek's article on "Bitwise Operator's", recommended!

Carycaryatid

Answer 6

for additional info

x += 1;    // x = x + 1;
x *= 2;    // x = x * 2;
x >>= 1 ;  // x = x >> 1;

Shifting binary is multipling or dividing by 2.

15 / 2 == 7 (rounded)
0b1110 >> 1 == 0b0111

You can think with decimal. Shifting decimal to right once is equivalent to dividing by 10.

530 / 10 == 53

Reason why people use shift rather than mul or div sometimes is : Shifting is faster than multipling, and much faster than dividing. If it's about speed, you should consider it. similarly, (x & 1) is faster than using (x % 2).

& and >> are bit manipulator, which are fatest calculations.

Halflight

Whoever downvotes, please give feedback as a comment, especially for new contributors. – Punchboard

"Especially when it's float" unclear what you mean by that. Binary shift operators operate on integers – Hardan

@Punchboard such a warm guy. thanks. – Halflight

@Hardan I don't know why I was saying that. Thank you for your feedback. I edited it. Maybe I was just thinking that floating division is very slow. I think rest of my answer still useful. – Halflight