DEV Community

Daniel Mantovani
Daniel Mantovani

Posted on

2 2

Perl Weekly Challenge #79,Task #1

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
$> _

Imagine monitoring actually built for developers

Billboard image

Join Vercel, CrowdStrike, and thousands of other teams that trust Checkly to streamline monitor creation and configuration with Monitoring as Code.

Start Monitoring

Top comments (0)

Image of Bright Data

Maintain Seamless Data Collection – No more rotating IPs or server bans.

Avoid detection with our dynamic IP solutions. Perfect for continuous data scraping without interruptions.

Avoid Detection

👋 Kindness is contagious

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

A simple "thank you" can uplift someone's spirits. Express your appreciation in the comments section!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay