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 ?

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

hemanth_1's gravatar image

6★hemanth_1
1.4k12
accept rate: 28%

edited 14 Mar '17, 19:27

Have u frame this question by yourself? Or it is been given somewhere?

(14 Mar '17, 20:51) bansal12325★

This was in a contest, I was not able to solve it

(14 Mar '17, 21:42) hemanth_16★

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) hemanth_16★

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

link

answered 14 Mar '17, 19:10

adhish_kapoor's gravatar image

3★adhish_kapoor
90410
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) bansal12325★

@bansal1232 Is __builtin_popcount an efficient way to do?

(14 Mar '17, 19:49) adhish_kapoor3★

__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 <iostream>
using namespace std;

int main() {

cout  << __builtin_popcount(15);

return 0;

}

Output : 4

link

answered 14 Mar '17, 19:43

a_n_b's gravatar image

4★a_n_b
211
accept rate: 0%

edited 14 Mar '17, 19:43

we are talking about 10^4 digits here

(14 Mar '17, 20:52) aminuteman1★

Is the number given in decimal representation?

link

answered 14 Mar '17, 19:00

bansal1232's gravatar image

5★bansal1232
2.8k1419
accept rate: 16%

Yes, its given in decimal

(14 Mar '17, 19:02) hemanth_16★

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

link

answered 14 Mar '17, 19:08

yb4singh's gravatar image

4★yb4singh
1215
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) hemanth_16★
toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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