blob: 068be81e2abd204aa23bf4a1424a857aea87efeb (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
## Please see file perltidy.ERR
# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
#=============================================================================
# CountSetBit.pm
#=============================================================================
# Copyright (c) 2020, Bob Lied
#=============================================================================
# Description:
#=============================================================================
package CountSetBit;
use strict;
use warnings;
use v5.30;
use feature qw/ signatures /;
no warnings qw/ experimental::signatures /;
require Exporter;
our @ISA = qw(Exporter);
our @EXPORT = qw();
our @EXPORT_OK = qw();
sub new ( $class, $n )
{
$class = ref($class) || $class;
my $self = {
_n => $n,
_sum => 0, };
bless $self, $class;
return $self;
}
# https://www.techiedelight.com/brian-kernighans-algorithm-count-set-bits-integer/
sub run($self)
{
$self->{_sum} += $self->_bitsOf($_) for ( 1 .. $self->{_n} );
return ( $self->{_sum} % 1000000007 );
}
sub _bitsOf ( $self, $n )
{
my $count = 0;
while ( $n > 0 )
{
$count++;
$n = $n & ( $n - 1 );
}
return $count;
}
1;
|
