Task: Count Set Bits

You are given a positive number $N. Write a script to count the total numbrer of set bits of the binary representations of all numbers from 1 to $N and return $total_count_set_bit % 1000000007.

Proposed Answer:

Note that perl already has the capability to get a binary expression of an integer, just using the sprintf formatter %b, as in

my $binary_string = sprintf("%b", $number);

We need to count how many "1"s are in the binary representation. There are many ways to do that in perl. We will use the return value of the transliteration internal function of perl (tr):

$amount_of_ones = $binary_string =~ tr/1//;

This will efectively remove all "1"s from our string, but most important, will return a scalar with the amount of substitutions done (i.e, number of 1s in the binary representation)

Also we are supposed to truncate to a modulo 1,000,000,007 integer on every addition, probably avoiding any overflows on perl arithmetic for 32 bit perls (that number is a prime number often used for that purpose).

So with all these considerations, our script will just be:

use strict;
use warnings;
use v5.20;

my $big_prime           = 1_000_000_007;
my $total_count_set_bit = 0;

for my $n (1 .. shift) {    # or $ARGV[0]
  $total_count_set_bit += sprintf("%b", $n) =~ tr/1//;
  $total_count_set_bit %= $big_prime;
}

say $total_count_set_bit;

As an example, you can use the script like this:

$> perl ch-1.pl 12345678
143433315
$> _