Second speedy solution for Binary Count by RRRQ - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Second solution in Speedy category for Binary Count by RRRQ

def checkio(number):
    cnt = 0

    while number:
        num32 = number & 0xFFFFFFFF
        number = number >> 32
        
        a = (num32 & 0xAAAAAAAA) >> 1
        b = (num32 & 0x55555555)
        num32 = a + b
    
        a = (num32 & 0xCCCCCCCC) >> 2
        b = (num32 & 0x33333333)
        num32 = a + b
    
        a = (num32 & 0xF0F0F0F0) >> 4
        b = (num32 & 0x0F0F0F0F)
        num32 = a + b
    
        a = (num32 & 0xFF00FF00) >> 8
        b = (num32 & 0x00FF00FF)
        num32 = a + b
    
        a = (num32 & 0xFFFF0000) >> 16
        b = (num32 & 0x0000FFFF)
        num32 = a + b
        
        cnt += num32

    return cnt

Feb. 21, 2014

Comments:

odwl on March 2, 2014, 8:59 p.m.
Is that faster than using bin?

RRRQ on March 3, 2014, 7:47 a.m.
yes. bin order is o( n ). this algorithm order is o( log(n) )

veky on March 3, 2014, 1:15 p.m.
Have you done any testing, or are you just superstitious? :-) (I'm not saying you're wrong, just that you can't be so sure without profiling.)

RRRQ on March 3, 2014, 1:58 p.m.
I've tested in c++ not python. so, if python's syntactic parsing implement was fool, this program is not speedy.

veky on March 3, 2014, 2:23 p.m.
That's one concern. There is another, that completely changes the game: C++ int is fixed-size, Python's is not. So, even if it works as you intended it to, it is still linear in groups of 32 bits. And since classical complexity theory disregards multiplicative constants and also finitely many first values when determining what's bigger, these two are completely incomparable. :-]

odwl on March 3, 2014, 5:45 p.m.
I just timed it it: with a long input: checkio(123123123123123453425364748472365263748) on 100000 runs Your algorithm: 1.045 sec the bin(number).count('1') algorithm: 0.117 sec So the bin algo in ~10x faster in that case. on double size input: your: 2.351 sec bin: 0.191 sec 4 * the size of input: your:4.42344689369 bin: 0.359971046448 So it seems that veky is right. : implicit loops in python are often a lot better than explicit ones. Your are rarely better of to 'rewrite' a fast implementation.

GitHub

0 %

You ClassRoom Demo is Ready With the new tool CheckiO ClassRoom, you will be able to analyze your students' progress, have your own leaderboard, change missions order on the map, and so on.