Population count
The population count is the number of 1's (ones) in the binary representation of a non-negative integer.
Population count is also known as pop count, popcount, sideways sum, and Hamming weight.
- For example, (which is 101 in binary) has a population count of .
Evil numbers are non-negative integers that have an even population count.
Odious numbers are positive integers that have an odd population count.
- Task requirements
- write a function (or routine) to return the population count of a non-negative integer.
- all computation of the lists below should start with 0 (zero).
- display the pop count of the 1st thirty powers of ().
- display the 1st thirty evil numbers.
- display the 1st thirty odious numbers.
- display each list of integers on one line (which may or may not include a title), each set of integers being shown should be properly identified.
- See also
- Sequence A000069 odious numbers on The On-Line Encyclopedia of Integer Sequences.
- Sequence A001969 evil numbers on The On-Line Encyclopedia of Integer Sequences.
Ada
Specifiction and implementation of an auxiliary package "Population_Count". The same package is used for Pernicious numbers#Ada
<lang ada>with Interfaces;
package Population_Count is
subtype Num is Interfaces.Unsigned_64; function Pop_Count(N: Num) return Natural;
end Population_Count;</lang>
<lang Ada>package body Population_Count is
function Pop_Count(N: Num) return Natural is
use Interfaces;
K5555: constant Unsigned_64 := 16#5555555555555555#;
K3333: constant Unsigned_64 := 16#3333333333333333#;
K0f0f: constant Unsigned_64 := 16#0f0f0f0f0f0f0f0f#;
K0101: constant Unsigned_64 := 16#0101010101010101#;
X: Unsigned_64 := N;
begin
X := X - (Shift_Right(X, 1) and k5555);
X := (X and k3333) + (Shift_Right(X, 2) and k3333);
X := (X + (Shift_Right(X, 4)) and K0f0f);
X := Shift_Right((x * k0101), 56);
return Natural(X);
end Pop_Count;
end Population_Count;</lang>
The main program:
<lang Ada>with Ada.Text_IO, Population_Count; use Ada.Text_IO; use Population_Count;
procedure Test_Pop_Count is
X: Num; use type Num;
begin
Put("Pop_Cnt(3**i):"); -- print pop_counts of powers of three
X := 1; -- X=3**0
for I in 1 .. 30 loop
Put(Natural'Image(Pop_Count(X)));
X := X * 3;
end loop;
New_Line;
Put("Evil: "); -- print first thirty evil numbers
X := 0;
for I in 1 .. 30 loop
while Pop_Count(X) mod 2 /= 0 loop -- X is not evil
X := X + 1;
end loop;
Put(Num'Image(X));
X := X + 1;
end loop;
New_Line;
Put("Odious: "); -- print thirty oudous numbers
X := 1;
for I in 1 .. 30 loop
while Pop_Count(X) mod 2 /= 1 loop -- X is not odious
X := X + 1;
end loop;
Put(Num'Image(X));
X := X + 1;
end loop;
New_Line;
end Test_Pop_Count;</lang>
- Output:
Pop_Cnt(3**i): 1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 Evil: 0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 Odious: 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59
AutoHotkey
<lang AutoHotkey>Loop, 30 Out1 .= PopCount(3 ** (A_Index - 1)) " " Loop, 60 i := A_Index - 1 , PopCount(i) & 0x1 ? Out3 .= i " " : Out2 .= i " " MsgBox, % "3^x:`t" Out1 "`nEvil:`t" Out2 "`nOdious:`t" Out3
PopCount(x) { ;https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation x -= (x >> 1) & 0x5555555555555555 , x := (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333) , x := (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f return (x * 0x0101010101010101) >> 56 }</lang>
- Output:
3^x: 1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 Evil: 0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 Odious: 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59
C
<lang c>#include <stdio.h>
int main() {
{
unsigned long long n = 1;
for (int i = 0; i < 30; i++) {
// __builtin_popcount() for unsigned int
// __builtin_popcountl() for unsigned long
// __builtin_popcountll() for unsigned long long
printf("%d ", __builtin_popcountll(n));
n *= 3;
}
printf("\n");
}
int od[30];
int ne = 0, no = 0;
printf("evil : ");
for (int n = 0; ne+no < 60; n++) {
if ((__builtin_popcount(n) & 1) == 0) {
if (ne < 30) {
printf("%d ", n); ne++;
}
} else {
if (no < 30) {
od[no++] = n;
}
}
}
printf("\n");
printf("odious: ");
for (int i = 0; i < 30; i++) {
printf("%d ", od[i]);
}
printf("\n");
return 0;
}</lang>
- Output:
1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 evil : 0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 odious: 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59
GCC's builtin doesn't exist prior to 3.4, and the LL version is broken in 3.4 to 4.1. In 4.2+, if the platform doesn't have a good popcount instruction or isn't enabled (e.g. not compiled with -march=native), it typically emits unoptimized code which is over 2x slower than the C below. Alternative:
<lang c>#if defined(__POPCNT__) && defined(__GNUC__) && (__GNUC__> 4 || (__GNUC__== 4 && __GNUC_MINOR__> 1))
- define HAVE_BUILTIN_POPCOUNTLL
- endif
static uint64_t bitcount64(uint64_t b) {
b -= (b >> 1) & 0x5555555555555555; b = (b & 0x3333333333333333) + ((b >> 2) & 0x3333333333333333); b = (b + (b >> 4)) & 0x0f0f0f0f0f0f0f0f; return (b * 0x0101010101010101) >> 56;
} /* For 32-bit, an 8-bit table may or may not be a little faster */ static uint32_t bitcount32(uint32_t b) {
b -= (b >> 1) & 0x55555555; b = (b & 0x33333333) + ((b >> 2) & 0x33333333); b = (b + (b >> 4)) & 0x0f0f0f0f; return (b * 0x01010101) >> 24;
}</lang>
C++
<lang cpp>#include <iostream>
- include <bitset>
- include <climits>
size_t popcount(unsigned long long n) {
return std::bitset<CHAR_BIT * sizeof n>(n).count();
}
int main() {
{
unsigned long long n = 1;
for (int i = 0; i < 30; i++) {
std::cout << popcount(n) << " ";
n *= 3;
}
std::cout << std::endl;
}
int od[30];
int ne = 0, no = 0;
std::cout << "evil : ";
for (int n = 0; ne+no < 60; n++) {
if ((popcount(n) & 1) == 0) {
if (ne < 30) {
std::cout << n << " "; ne++;
}
} else {
if (no < 30) {
od[no++] = n;
}
}
}
std::cout << std::endl;
std::cout << "odious: ";
for (int i = 0; i < 30; i++) {
std::cout << od[i] << " ";
}
std::cout << std::endl;
return 0;
}</lang>
- Output:
1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 evil : 0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 odious: 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59
C#
<lang csharp> using System; using System.Linq;
namespace PopulationCount {
class Program
{
private static int PopulationCount(long n)
{
string binaryn = Convert.ToString(n, 2);
return binaryn.ToCharArray().Where(t => t == '1').Count();
}
static void Main(string[] args)
{
Console.WriteLine("Population Counts:");
Console.Write("3^n : ");
int count = 0;
while (count < 30)
{
double n = Math.Pow(3f, (double)count);
int popCount = PopulationCount((long)n);
Console.Write(string.Format("{0} ", popCount));
count++;
}
Console.WriteLine();
Console.Write("Evil: ");
count = 0;
int i = 0;
while (count < 30)
{
int popCount = PopulationCount(i);
if (popCount % 2 == 0)
{
count++;
Console.Write(string.Format("{0} ", i));
}
i++;
}
Console.WriteLine();
Console.Write("Odious: ");
count = 0;
i = 0;
while (count < 30)
{
int popCount = PopulationCount(i);
if (popCount % 2 != 0)
{
count++;
Console.Write(string.Format("{0} ", i));
}
i++;
}
Console.ReadKey();
}
}
} </lang>
- Output:
Population Counts: 3^n : 1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 Evil: 0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 Odious: 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59
Common Lisp
<lang lisp>(format T "3^x: ~{~a ~}~%"
(loop for i below 30
collect (logcount (expt 3 i))))
(multiple-value-bind
(evil odious)
(loop for i below 60
if (evenp (logcount i)) collect i into evil
else collect i into odious
finally (return (values evil odious)))
(format T "evil: ~{~a ~}~%" evil)
(format T "odious: ~{~a ~}~%" odious))</lang>
- Output:
3^x: 1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 evil: 0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 odious: 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59
D
<lang d>void main() {
import std.stdio, std.algorithm, std.range, core.bitop;
enum pCount = (ulong n) => popcnt(n & uint.max) + popcnt(n >> 32);
writefln("%s\nEvil: %s\nOdious: %s",
uint.max.iota.map!(i => pCount(3L ^^ i)).take(30),
uint.max.iota.filter!(i => pCount(i) % 2 == 0).take(30),
uint.max.iota.filter!(i => pCount(i) % 2).take(30));
}</lang>
- Output:
[1, 2, 2, 4, 3, 6, 6, 5, 6, 8, 9, 13, 10, 11, 14, 15, 11, 14, 14, 17, 17, 20, 19, 22, 16, 18, 24, 30, 25, 25] Evil: [0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30, 33, 34, 36, 39, 40, 43, 45, 46, 48, 51, 53, 54, 57, 58] Odious: [1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35, 37, 38, 41, 42, 44, 47, 49, 50, 52, 55, 56, 59]
Erlang
<lang erlang>-module(population_count). -export([popcount/1]).
-export([task/0]).
popcount(N) ->
popcount(N,0).
popcount(0,Acc) ->
Acc;
popcount(N,Acc) ->
popcount(N div 2, Acc + N rem 2).
threes(_,0,Acc) ->
lists:reverse(Acc);
threes(Threes,N,Acc) ->
threes(Threes * 3, N-1, [popcount(Threes)|Acc]).
threes(N) ->
threes(1,N,[]).
evil(_,0,Acc) ->
lists:reverse(Acc);
evil(N,Count,Acc) ->
case popcount(N) rem 2 of
0 ->
evil(N+1,Count-1,[N|Acc]);
1 ->
evil(N+1,Count,Acc)
end.
evil(Count) ->
evil(0,Count,[]).
odious(_,0,Acc) ->
lists:reverse(Acc);
odious(N,Count,Acc) ->
case popcount(N) rem 2 of
1 ->
odious(N+1,Count-1,[N|Acc]);
0 ->
odious(N+1,Count,Acc)
end.
odious(Count) ->
odious(1,Count,[]).
task() ->
io:format("Powers of 3: ~p~n",[threes(30)]),
io:format("Evil:~p~n",[evil(30)]),
io:format("Odious:~p~n",[odious(30)]).</lang>
- Output:
<lang erlang>61> population_count:task(). Powers of 3: [1,2,2,4,3,6,6,5,6,8,9,13,10,11,14,15,11,14,14,17,17,20,19,22,16,18,24,30,25,
25]
Evil:[0,3,5,6,9,10,12,15,17,18,20,23,24,27,29,30,33,34,36,39,40,43,45,46,48,
51,53,54,57,58]
Odious:[1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31,32,35,37,38,41,42,44,47,49,
50,52,55,56,59]
ok</lang>
Fortran
<lang fortran>program population_count
implicit none
integer, parameter :: i64 = selected_int_kind(18) integer(i64) :: x integer :: i, n x = 1 write(*, "(a8)", advance = "no") "3**i :" do i = 1, 30 write(*, "(i3)", advance = "no") popcnt(x) x = x * 3 end do
write(*,*)
write(*, "(a8)", advance = "no") "Evil :"
n = 0
x = 0
do while(n < 30)
if(mod(popcnt(x), 2) == 0) then
n = n + 1
write(*, "(i3)", advance = "no") x
end if
x = x + 1
end do
write(*,*)
write(*, "(a8)", advance = "no") "Odious :"
n = 0
x = 0
do while(n < 30)
if(mod(popcnt(x), 2) /= 0) then
n = n + 1
write(*, "(i3)", advance = "no") x
end if
x = x + 1
end do
contains
integer function popcnt(x)
integer(i64), intent(in) :: x integer :: i
popcnt = 0 do i = 0, 63 if(btest(x, i)) popcnt = popcnt + 1 end do
end function end program</lang>
- Output:
3**i : 1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 Evil : 0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 Odious : 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59
Go
<lang go>package main
import "fmt"
func pop64(w uint64) int {
const (
ff = 1<<64 - 1
mask1 = ff / 3
mask3 = ff / 5
maskf = ff / 17
maskp = maskf >> 3 & maskf
)
w -= w >> 1 & mask1
w = w&mask3 + w>>2&mask3
w = (w + w>>4) & maskf
return int(w * maskp >> 56)
}
func main() {
fmt.Println("Pop counts, powers of 3:")
n := uint64(1) // 3^0
for i := 0; i < 30; i++ {
fmt.Printf("%d ", pop64(n))
n *= 3
}
fmt.Println()
fmt.Println("Evil numbers:")
var od [30]uint64
var ne, no int
for n = 0; ne+no < 60; n++ {
if pop64(n)&1 == 0 {
if ne < 30 {
fmt.Printf("%d ", n)
ne++
}
} else {
if no < 30 {
od[no] = n
no++
}
}
}
fmt.Println()
fmt.Println("Odious numbers:")
for _, n := range od {
fmt.Printf("%d ", n)
}
fmt.Println()
}</lang>
- Output:
Pop counts, powers of 3: 1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 Evil numbers: 0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 Odious numbers: 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59
Haskell
<lang haskell>import Data.Bits (popCount)
printPops :: (Show a, Integral a) => String -> [a] -> IO () printPops title counts = putStrLn $ title ++ show (take 30 counts)
main :: IO () main = do
printPops "popcount " $ map popCount $ iterate (*3) (1 :: Integer) printPops "evil " $ filter (even . popCount) ([0..] :: [Integer]) printPops "odious " $ filter ( odd . popCount) ([0..] :: [Integer])</lang>
- Output:
popcount [1,2,2,4,3,6,6,5,6,8,9,13,10,11,14,15,11,14,14,17,17,20,19,22,16,18,24,30,25,25] evil [0,3,5,6,9,10,12,15,17,18,20,23,24,27,29,30,33,34,36,39,40,43,45,46,48,51,53,54,57,58] odious [1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31,32,35,37,38,41,42,44,47,49,50,52,55,56,59]
J
Implementation:
<lang J>pcount=: +/"1@#:</lang>
Task:
<lang J> pcount 3^i.30x 1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25
30{.(#~ 1=2|pcount) i. 100 NB. odd population count (aka "ODious numbers")
1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59
30{.(#~ 0=2|pcount) i. 100 NB. even population count (aka "EVil numbers")
0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58</lang>
Java
<lang java>import java.math.BigInteger;
public class PopCount {
public static void main(String[] args) {
{ // with int System.out.print("32-bit integer: "); int n = 1; for (int i = 0; i < 20; i++) { System.out.printf("%d ", Integer.bitCount(n)); n *= 3; } System.out.println(); } { // with long System.out.print("64-bit integer: "); long n = 1; for (int i = 0; i < 30; i++) { System.out.printf("%d ", Long.bitCount(n)); n *= 3; } System.out.println(); } { // with BigInteger System.out.print("big integer : "); BigInteger n = BigInteger.ONE; BigInteger three = BigInteger.valueOf(3); for (int i = 0; i < 30; i++) { System.out.printf("%d ", n.bitCount()); n = n.multiply(three); } System.out.println(); }
int[] od = new int[30]; int ne = 0, no = 0; System.out.print("evil : "); for (int n = 0; ne+no < 60; n++) { if ((Integer.bitCount(n) & 1) == 0) { if (ne < 30) { System.out.printf("%d ", n); ne++; } } else { if (no < 30) { od[no++] = n; } } } System.out.println(); System.out.print("odious : "); for (int n : od) { System.out.printf("%d ", n); } System.out.println();
}
}</lang>
- Output:
32-bit integer: 1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 64-bit integer: 1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 big integer : 1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 evil : 0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 odious : 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59
jq
<lang jq>def popcount:
def bin: recurse( if . == 0 then empty else ./2 | floor end ) % 2; [bin] | add;
def firstN(count; condition):
if count > 0 then if condition then ., (1+.| firstN(count-1; condition)) else (1+.) | firstN(count; condition) end else empty end;
def task:
def pow(n): . as $m | reduce range(0;n) as $i (1; . * $m);
"The pop count of the first thirty powers of 3:", [range(0;30) as $n | 3 | pow($n) | popcount],
"The first thirty evil numbers:", [0 | firstN(30; (popcount % 2) == 0)],
"The first thirty odious numbers:", [0 | firstN(30; (popcount % 2) == 1)]
task</lang>
- Output:
$ jq -n -r -c -f Population_count.jq The pop count of the first thirty powers of 3: [1,2,2,4,3,6,6,5,6,8,9,13,10,11,14,15,11,14,14,17,17,20,19,22,16,18,24,30,25,25] The first thirty evil numbers: [0,3,5,6,9,10,12,15,17,18,20,23,24,27,29,30,33,34,36,39,40,43,45,46,48,51,53,54,57,58] The first thirty odious numbers: [1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31,32,35,37,38,41,42,44,47,49,50,52,55,56,59]
Julia
<lang Julia>julia> popcount(n) = sum(digits(n,2)) ; show([popcount(3^n) for n =0:29]) [1,2,2,4,3,6,6,5,6,8,9,13,10,11,14,15,11,14,14,17,17,20,19,22,16,18,24,30,25,25]
julia> println("evil numbers:") ; show(filter(x->iseven(popcount(x)), [0:59])) evil numbers: [0,3,5,6,9,10,12,15,17,18,20,23,24,27,29,30,33,34,36,39,40,43,45,46,48,51,53,54,57,58]
julia> println("odious numbers:") ; show(filter(x->isodd(popcount(x)), [0:59])) odious numbers: [1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31,32,35,37,38,41,42,44,47,49,50,52,55,56,59]</lang>
Mathematica
<lang Mathematica>popcount[n_Integer] := IntegerDigits[n, 2] // Total Print["population count of powers of 3"] popcount[#] & /@ (3^Range[0, 30]) (*******) evilQ[n_Integer] := popcount[n] // EvenQ evilcount = 0; evillist = {}; i = 0; While[evilcount < 30,
If[evilQ[i], AppendTo[evillist, i]; evilcount++]; i++ ]
Print["first thirty evil numbers"] evillist (*******) odiousQ[n_Integer] := popcount[n] // OddQ odiouscount = 0; odiouslist = {}; i = 0; While[odiouscount < 30,
If[odiousQ[i], AppendTo[odiouslist, i]; odiouscount++]; i++ ]
Print["first thirty odious numbers"] odiouslist</lang>
- Output:
population count of powers of 3
{1, 2, 2, 4, 3, 6, 6, 5, 6, 8, 9, 13, 10, 11, 14, 15, 11, 14, 14, 17, 17, 20, 19, 22, 16, 18, 24, 30, 25, 25, 25}
first thirty evil numbers
{0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30, 33, 34, 36, 39, 40, 43, 45, 46, 48, 51, 53, 54, 57, 58}
first thirty odious numbers
{1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35, 37, 38, 41, 42, 44, 47, 49, 50, 52, 55, 56, 59}
PARI/GP
<lang parigp>vector(30,n,hammingweight(3^(n-1))) od=select(n->hammingweight(n)%2,[0..100]); ev=setminus([0..100],od); ev[1..30] od[1..30]</lang>
- Output:
%1 = [1, 2, 2, 4, 3, 6, 6, 5, 6, 8, 9, 13, 10, 11, 14, 15, 11, 14, 14, 17, 17, 20, 19, 22, 16, 18, 24, 30, 25, 25] %2 = [0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30, 33, 34, 36, 39, 40, 43, 45, 46, 48, 51, 53, 54, 57, 58] %3 = [1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35, 37, 38, 41, 42, 44, 47, 49, 50, 52, 55, 56, 59]
Perl
We'll emulate infinite lists with closures.
<lang perl>use strict; use warnings;
sub population_count {
my $n = shift;
die "argument can't be negative" if $n < 0;
my $c;
for ($c = 0; $n; $n >>= 1) {
$c += $n & 1;
}
$c;
}
print join ' ', map { population_count(3**$_) } 0 .. 30 - 1; print "\n"; sub evil {
my $i = 0;
sub { $i++ while population_count($i) % 2; $i++ }
} sub odious {
my $i = 0;
sub { $i++ until population_count($i) % 2; $i++ }
}
my ($evil, $odious) = (evil, odious); my (@evil, @odious); for (1 .. 30) {
push @evil, $evil->(); push @odious, $odious->();
}
printf "Evil : %s\n", join ' ', @evil; printf "Odious: %s\n", join ' ', @odious;</lang>
- Output:
1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 Evil : 0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 Odious: 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59
A faster population count can be done with pack/unpack:
<lang>say unpack("%b*",pack "J*", 1234567); # J = UV</lang>
Various modules can also perform a population count, with the first of these being faster than the pack/unpack builtins. The first two easily support bigints, the third will with some adjustment. <lang perl>use ntheory qw/hammingweight/; say hammingweight(1234567);
use Math::GMPz qw/Rmpz_popcount/; say Rmpz_popcount(Math::GMPz->new(1234567));
use Bit::Vector; say Bit::Vector->new_Dec(64,1234567)->Norm;</lang>
Perl 6
<lang perl6>sub population-count(Int $n where * >= 0) { [+] $n.base(2).comb }
say map &population-count, 3 «**« ^30; say "Evil: ", (grep { population-count($_) %% 2 }, 0 .. *)[^30]; say "Odious: ", (grep { population-count($_) % 2 }, 0 .. *)[^30];</lang>
- Output:
1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 Evil: 0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 Odious: 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59
That's the convenient way to write it, but the following avoids string processing and is therefore about twice as fast: <lang perl6>sub population-count(Int $n is copy where * >= 0) {
loop (my $c = 0; $n; $n +>= 1) {
$c += $n +& 1;
}
$c;
}</lang>
Python
<lang python>>>> def popcount(n): return bin(n).count("1") ... >>> [popcount(3**i) for i in range(30)] [1, 2, 2, 4, 3, 6, 6, 5, 6, 8, 9, 13, 10, 11, 14, 15, 11, 14, 14, 17, 17, 20, 19, 22, 16, 18, 24, 30, 25, 25] >>> evil, odious, i = [], [], 0 >>> while len(evil) < 30 or len(odious) < 30: ... p = popcount(i) ... if p % 2: odious.append(i) ... else: evil.append(i) ... i += 1 ... >>> evil[:30] [0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30, 33, 34, 36, 39, 40, 43, 45, 46, 48, 51, 53, 54, 57, 58] >>> odious[:30] [1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35, 37, 38, 41, 42, 44, 47, 49, 50, 52, 55, 56, 59] >>> </lang>
Racket
<lang racket>#lang racket
- Positive version from "popcount_4" in
- https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation
- negative version follows R6RS definition documented in
- http://docs.racket-lang.org/r6rs/r6rs-lib-std/r6rs-lib-Z-H-12.html?q=bitwise-bit#node_idx_1074
(define (population-count n)
(if (negative? n)
(bitwise-not (population-count (bitwise-not n)))
(let inr ((x n) (rv 0))
(if (= x 0) rv (inr (bitwise-and x (sub1 x)) (add1 rv))))))
(define (evil? x)
(and (not (negative? x))
(even? (population-count x))))
(define (odious? x)
(and (positive? x)
(odd? (population-count x))))
(define tasks
(list "display the pop count of the 1st thirty powers of 3 (3^0, 3^1, 3^2, 3^3, 3^4, ...)." (for/list ((i (in-range 30))) (population-count (expt 3 i))) "display the 1st thirty evil numbers." (for/list ((_ (in-range 30)) (e (sequence-filter evil? (in-naturals)))) e) "display the 1st thirty odious numbers." (for/list ((_ (in-range 30)) (o (sequence-filter odious? (in-naturals)))) o)))
(for-each displayln tasks)
(module+ test
(require rackunit) (check-equal? (for/list ((p (sequence-map population-count (in-range 16)))) p) '(0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4)) (check-true (evil? 0) "0 has just *got* to be evil") (check-true (evil? #b011011011) "six bits... truly evil") (check-false (evil? #b1011011011) "seven bits, that's odd!") (check-true (odious? 1) "the least odious number") (check-true (odious? #b1011011011) "seven (which is odd) bits") (check-false (odious? #b011011011) "six bits... is evil"))</lang>
- Output:
display the pop count of the 1st thirty powers of 3 (3^0, 3^1, 3^2, 3^3, 3^4, ...). (1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25) display the 1st thirty evil numbers. (0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58) display the 1st thirty odious numbers. (1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59)
REXX
<lang rexx>/*REXX program counts the (binary) bits in the binary version of a dec#,*/ /* and also generates a specific number of EVIL and ODIOUS numbers. */ parse arg N B . /*get optional arguments, N and B*/ if N== | N==',' then N=30 /*N given? Then use the default.*/ if B== | B==',' then B= 3 /*B given? Then use the default.*/ numeric digits 3000 /*support most gi-normus numbers.*/ numeric digits max(20,length(B**N)) /*whittle the precision to size. */
/* [↑] a little calc for sizing.*/
$=; do j=0 for N /*generate N popCounts for powers*/
$=$ popCount(B**j) /*get the popCount for a pow of B*/
end /*j*/ /* [↑] append popCount to a list*/
/* [↓] display the pop counts. */
call showList 'popcounts of the powers of' B /*display list with hdr.*/
do j=0 until #==N /*generate N evil numbers. */
if popCount(j)//2 then iterate /*if odd population count, skip.*/
#=#+1 /*bump the evil number counter.*/
$=$ j /*append an evil # to a list.*/
end /*j*/ /* [↑] build a list of evil #s. */
/* [↓] display the evil # list. */
call showList 'evil numbers' /*display the list with a header.*/
do j=0 until #==N /*generate N odious numbers. */
if popCount(j)//2==0 then iterate /*if even population count, skip.*/
#=#+1 /*bump the odious number counter.*/
$=$ j /*append an odious # to a list.*/
end /*j*/ /* [↑] build a list of odious #s*/
/* [↓] display the odious# list.*/
call showList 'odious numbers' /*display the list with a header.*/ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────D2B subroutine──────────────────────*/ d2b: return word(strip(x2b(d2x(arg(1))),'L',0) 0,1) /*convert dec──►bin*/ /*──────────────────────────────────POPCOUNT subroutine─────────────────*/ popCount: procedure;_=d2b(abs(arg(1))) /*convert the # passed to binary.*/ return length(_)-length(space(translate(_,,1),0)) /*count the one bits.*/ /*──────────────────────────────────SHOWLIST subroutine─────────────────*/ showlist: say; say 'The 1st' N arg(1)':'; say substr($,2); #=0; $=; return</lang> output when using the default input:
The 1st 30 popcounts of the powers of 3: 1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 The 1st 30 evil numbers: 0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 The 1st 30 odious numbers: 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59
Ruby
Demonstrating lazy enumerators. <lang ruby>class Integer
def popcount
self.to_s(2).count("1")
end
def evil? self >= 0 && popcount.even? end
def odious? self > 0 && popcount.odd? end
end
inf = 1.0 / 0.0 # Infinity puts "Powers of 3:", (0...30).map{|n| (3**n).popcount}.join(' ') puts "Evil:" , (0..inf).lazy.select(&:evil? ).first(30).join(' ') puts "Odious:", (0..inf).lazy.select(&:odious?).first(30).join(' ')</lang>
- Output:
Powers of 3: 1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 Evil: 0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 Odious: 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59
Seed7
The function popcount below converts
the integer into a bitset.
The function card
is used to compute the population count of the bitset.
<lang seed7>$ include "seed7_05.s7i";
const func integer: popcount (in integer: n) is
return card(bitset conv n);
const proc: main is func
local
var integer: count is 0;
var integer: num is 0;
begin
for count range 0 to 29 do
write(popcount(3 ** count) <& " ");
end for;
writeln;
write("evil: ");
for count range 1 to 30 do
while odd(popcount(num)) do
incr(num);
end while;
write(num <& " ");
incr(num);
end for;
writeln;
write("odious: ");
num := 0;
for count range 1 to 30 do
while not odd(popcount(num)) do
incr(num);
end while;
write(num <& " ");
incr(num);
end for;
writeln;
end func;
</lang>
- Output:
1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 evil: 0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 odious: 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59
Tcl
<lang tcl>package require Tcl 8.6
proc hammingWeight {n} {
tcl::mathop::+ {*}[split [format %llb $n] ""]
} for {set n 0;set l {}} {$n<30} {incr n} {
lappend l [hammingWeight [expr {3**$n}]]
} puts "p3: $l" for {set n 0;set e [set o {}]} {[llength $e]<30||[llength $o]<30} {incr n} {
lappend [expr {[hammingWeight $n]&1 ? "o" : "e"}] $n
} puts "evil: [lrange $e 0 29]" puts "odious: [lrange $o 0 29]"</lang>
- Output:
p3: 1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 evil: 0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 odious: 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59
UNIX Shell
<lang bash>popcount() {
local -i n=$1
(( n < 0 )) && return 1
local ones=0
while (( n > 0 )); do
(( ones += n%2 ))
(( n /= 2 ))
done
echo $ones
}
popcount_3s=() n=1 for (( i=0; i<30; i++ )); do
popcount_3s+=( $(popcount $n) ) (( n *= 3 ))
done echo "powers of 3 popcounts: ${popcount_3s[*]}"
evil=() odious=() n=0 while (( ${#evil[@]} < 30 || ${#odious[@]} < 30 )); do
p=$( popcount $n )
if (( $p%2 == 0 )); then
evil+=( $n )
else
odious+=( $n )
fi
(( n++ ))
done echo "evil nums: ${evil[*]:0:30}" echo "odious nums: ${odious[*]:0:30}"</lang>
- Output:
powers of 3 popcounts: 1 2 2 4 3 6 6 5 6 8 9 13 10 11 14 15 11 14 14 17 17 20 19 22 16 18 24 30 25 25 evil nums: 0 3 5 6 9 10 12 15 17 18 20 23 24 27 29 30 33 34 36 39 40 43 45 46 48 51 53 54 57 58 odious nums: 1 2 4 7 8 11 13 14 16 19 21 22 25 26 28 31 32 35 37 38 41 42 44 47 49 50 52 55 56 59
zkl
Ints have the 1s count as a property. <lang zkl>n:=1; do(30){print(n.num1s,","); n*=3} println();
println("evil: ",(0).walker(*).tweak(fcn(n){
if(n.num1s.isOdd)Void.Skip else n}).walk(30).concat(","))
println("odious: ",(0).walker(*).tweak(fcn(n){
if(n.num1s.isEven)Void.Skip else n}).walk(30).concat(","))</lang>
- Output:
1,2,2,4,3,6,6,5,6,8,9,13,10,11,14,15,11,14,14,17,17,20,19,22,16,18,24,30,25,25, evil: 0,3,5,6,9,10,12,15,17,18,20,23,24,27,29,30,33,34,36,39,40,43,45,46,48,51,53,54,57,58 odious: 1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31,32,35,37,38,41,42,44,47,49,50,52,55,56,59