72

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++

Prateek Gupta
  • 119
  • 2
  • 7
Sandra K
  • 1,209
  • 1
  • 10
  • 21
  • 16
    "_This question shows research efforts; It is useful and clear_" Then [**what's up with rude comments?**](http://meta.stackexchange.com/questions/15143/whats-with-all-the-rude-comments-recently/15144) and the downvotes?! – Khalil Khalaf Aug 12 '16 at 16:30
  • 14
    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. – Sergey Kalinichenko Aug 12 '16 at 16:37
  • 8
    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. – user4581301 Aug 12 '16 at 16:40
  • Strongly recommend getting [a good book](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list), but if this is not possible, a [good starter can be found here.](https://isocpp.org/tour). [Excellent technical documentation can be found here, often with examples.](http://en.cppreference.com/) – user4581301 Aug 12 '16 at 16:46
  • 2
    @user4581301 Thank you for the references I looked at all of them :) – Sandra K Aug 12 '16 at 23:17
  • Possible duplicate of [What does operator >>= mean](http://stackoverflow.com/questions/31925706/what-does-operator-mean) – Raymond Chen Jan 01 '17 at 16:04
  • 3
    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. – davmac Jan 01 '17 at 17:57
  • 7
    @RaymondChen: really bad idea to teach people to look at Javascript documentation to learn about C++ operators. – Ben Voigt Jan 01 '17 at 23:25
  • 1
    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. – M.M Jan 02 '17 at 23:14
  • 1
    Instead of `-1` you probably ought to use `~0U` to set all the bits to 1. – Eljay Mar 07 '18 at 03:51
  • Possible duplicate of [What are bitwise operators?](https://stackoverflow.com/questions/276706/what-are-bitwise-operators) – phuclv May 03 '19 at 01:37

5 Answers5

79

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.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • 1
    Hi and thanks. Could you please explain more on (depending on the last bit) and (shifted by one to the right)? – Sandra K Aug 12 '16 at 16:29
  • 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](http://stackoverflow.com/questions/7622/are-the-shift-operators-arithmetic-or-logical-in-c). – Ken Y-N Aug 12 '16 at 16:43
  • 3
    `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. – Maxim Egorushkin Aug 12 '16 at 16:46
  • 1
    @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! – Sergey Kalinichenko Aug 12 '16 at 16:51
  • @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. – Sergey Kalinichenko Aug 12 '16 at 16:51
  • 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. – Martin Bonner supports Monica Aug 12 '16 at 19:36
  • " For values of signed type the most significant bit is copied from the value prior to shifting," - not necessarily. – Martin Bonner supports Monica Aug 12 '16 at 19:39
57

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.

Jules Dupont
  • 7,259
  • 7
  • 39
  • 39
rama
  • 591
  • 4
  • 2
25

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.

stackomatiker
  • 324
  • 3
  • 14
  • 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 – Sandra K Feb 23 '18 at 14:37
  • E.g. you could use both operators for reversing the bits of an Integer. See the first example of: [Reverse Bits of Integer](http://www.techiedelight.com/reverse-bits-of-given-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](http://www.java2s.com/Code/CSharp/Language-Basics/Usetheshiftoperatorstomultiplyanddivideby2.htm) – stackomatiker Feb 23 '18 at 14:52
6

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)
Satyendra Yadav
  • 156
  • 3
  • 14
4

(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!

Matt Ke
  • 3,599
  • 12
  • 30
  • 49
Subit Nath
  • 41
  • 1