2

i am trying to count number of bits in 64 bit integer but it shows some unexpected.here is the code. counting bits is was not the major part but some unexpected output is....plz have a look on input and output!!!!

#include<iostream>
#include<math.h>
#include<stdint.h>
#include<cstdio>
using namespace std;

int64_t t,n,ans;
int main(){
    cin>>t;
    while(t--){
         int64_t ans=0;
         cin>>n;
         /*
         while(n>0LL){
             n>>=1LL;
             ans++;
         }//*/
        ans=floor(log2(n));
        //ans=floor(log2l(n));
        cout<<ans<<"\n";

    }
    return 0;
}

the input and output is this

10
18446744073709551615

63 (number of bits in 18446744073709551615) should be printed only once and console should be waiting till i input another number and the count the number of bits in other number.but it is not happening.The output comes is like this....

63
63
63
63
63
63
63
63
63
63

plz help me ragarding the same.

vkstack
  • 1,582
  • 11
  • 24
  • 3
    Ever heard of the shift operator?! – ypnos Aug 18 '15 at 19:19
  • y not google it. oh sorry, i realize the problem is more fundamental. the number of 1-bits is not given by any simple arithmetic expression. but the standard library is there for you: `std::bitset<64>( n ).count()`. – Cheers and hth. - Alf Aug 18 '15 at 19:19
  • by the way, using the preprocessor where you don't need, is likely to land you in trouble (extra work, like lots of it). instead of `#define ll long long`, include `` and use `uint64_t`. that also corrects two other problems: use of unreadable and easy to mistake identifier `ll` (few can see if that's I or l, do you see any difference?), and use of signed integer for bit manipulation, nix gut. – Cheers and hth. - Alf Aug 18 '15 at 19:24
  • 2
    See http://stackoverflow.com/questions/109023/ which is for 32 bits but the principle is the same. – Matthew Strawbridge Aug 18 '15 at 19:26
  • 1
    Perhaps you can generalize the answers to this question [How to count the number of set bits in a 32-bit integer](http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer?rq=1) – Bo Persson Aug 18 '15 at 19:27
  • 1
    18446744073709551615 is out of range for a signed `int_64`. You should call `cin.clear()` to clear the error flag on the input stream somewhere inside the loop. – Sven Marnach Aug 18 '15 at 19:34
  • And since the value is out of range, the stream is in an error state that returns immediately when you try to extract from it. – molbdnilo Aug 18 '15 at 19:40
  • @molbdnilo: Yep, that's what I was implying. – Sven Marnach Aug 18 '15 at 19:41

2 Answers2

3

On x86-64 there's the POPCNT instruction. https://en.wikipedia.org/wiki/SSE4#POPCNT_and_LZCNT

https://msdn.microsoft.com/en-us/library/bb385231.aspx

unsigned __int64 __popcnt64(
   unsigned __int64 value
);

GCC

__builtin_popcountll ((long long) x);
Louis Ricci
  • 20,804
  • 5
  • 48
  • 62
3

In addition to the above explanations how to properly count bits this is why it goes on until t exhausted without asking for more input:

Problem is in the size of your value: 18446744073709551615

It is bigger than signed long long. So, once you enter it into cin the stream becomes not good(): failbit is set:

failbit - Logical error on i/o operation

From here http://www.cplusplus.com/reference/istream/istream/operator%3E%3E/ :

Extracts and parses characters ... interpret them as ... the proper type... ...Then (if good), ...adjusting the stream's internal state flags accordingly.

So, in your case

  1. you read first value 18446744073709551615, failbit is set.
  2. you process whatever is in the n (should be numeric_limits<long long>::max()), ignoring any input errors
  3. you try reading next value
  4. since failbit is set cin>>n does nothing leaving old n as is
  5. this repeats until t exhausted
fukanchik
  • 2,811
  • 24
  • 29