You are not logged in. Please login at www.codechef.com to post your questions!

×

# How to find the number of set bits in large numbers ?

 1 By 'Large', I mean numbers containing up to 10^4 digits. I have tried doing it by converting the number to binary, digit by digit (representing numbers as a vector of bits), so I multiply the current result by 10 and add the next digit, which I have done by adding two numbers, left shifted 3 times and 1 time(because N*10 = N<<3 + N<<1) and then wrote a function that adds two binary numbers represented this way, and then add the next digit. But its too slow. asked 14 Mar '17, 18:56 1.4k●12 accept rate: 28% Have u frame this question by yourself? Or it is been given somewhere? (14 Mar '17, 20:51) This was in a contest, I was not able to solve it (14 Mar '17, 21:42) Got it accepted just now, it was slow because of the vector, I didn't consider the fact that insertion at front is slow with it, used a deque instead and it got accepted :) (14 Mar '17, 21:43)

 2 @hemanth_1 well,I would love to do it in python as.... n=int(input()) b=bin(n) ans=b.count("1") print(ans) Still u can find the way it could be done in c++.. answered 14 Mar '17, 19:10 904●10 accept rate: 9% 1 The main task is to solve this question in standard way. Please don't think that python will do anything. (14 Mar '17, 19:12) @bansal1232 Is __builtin_popcount an efficient way to do? (14 Mar '17, 19:49)
 2 __builtin_popcount() There is a built in gcc function called __builtin_popcount() which can calculate the set bits of a given number represented in decimal. i.e include using namespace std; int main() { cout << __builtin_popcount(15); return 0; }  Output : 4 answered 14 Mar '17, 19:43 4★a_n_b 21●1 accept rate: 0% we are talking about 10^4 digits here (14 Mar '17, 20:52)
 1 Is the number given in decimal representation? answered 14 Mar '17, 19:00 2.8k●1●4●19 accept rate: 16% Yes, its given in decimal (14 Mar '17, 19:02)
 1 You can simply find it in log(N) complexity by dividing it by 2 , But you have to do this operation in array representation of number answered 14 Mar '17, 19:08 4★yb4singh 121●5 accept rate: 0% If I represent the number as an array, and say, it has 'N' digits, wouldn't division by 2 take O(N) time ? and I'd have to do it Log 10^N times, which will roughly be the number of digits itself (correct me if I'm wrong). (14 Mar '17, 19:15)
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×166
×77
×12
×9

question asked: 14 Mar '17, 18:56

question was seen: 656 times

last updated: 14 Mar '17, 21:45