Population count: Difference between revisions
(→{{header|Go}}: show standard library function) |
|||
Line 751: | Line 751: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
===Standard Library=== |
|||
Method of WP example '''popcount_3'''. Probably fastest on machines with fast integer multiplication for data with lots of 1 bits. |
|||
As of Go 1.9, this function is in the standard Library. |
|||
<lang go>package main |
<lang go>package main |
||
import |
import ( |
||
⚫ | |||
"math/bits" |
|||
⚫ | |||
) |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
} |
|||
func main() { |
func main() { |
||
Line 774: | Line 764: | ||
n := uint64(1) // 3^0 |
n := uint64(1) // 3^0 |
||
for i := 0; i < 30; i++ { |
for i := 0; i < 30; i++ { |
||
fmt.Printf("%d ", |
fmt.Printf("%d ", bits.OnesCount64(n)) |
||
n *= 3 |
n *= 3 |
||
} |
} |
||
Line 782: | Line 772: | ||
var ne, no int |
var ne, no int |
||
for n = 0; ne+no < 60; n++ { |
for n = 0; ne+no < 60; n++ { |
||
if |
if bits.OnesCount64(n)&1 == 0 { |
||
if ne < 30 { |
if ne < 30 { |
||
fmt.Printf("%d ", n) |
fmt.Printf("%d ", n) |
||
Line 810: | Line 800: | ||
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 |
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 |
||
</pre> |
</pre> |
||
===Implementation=== |
|||
''' |
|||
Method of WP example ''' |
Method of WP example '''popcount_3''': |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
) |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
}</lang> |
|||
Method of WP example '''popcount_4''': |
|||
<lang go>func pop64(w uint64) (c int) { |
<lang go>func pop64(w uint64) (c int) { |
||
for w != 0 { |
for w != 0 { |
Revision as of 16:42, 11 September 2017
You are encouraged to solve this task according to the task description, using any language you may know.
The population count is the number of 1s (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, 5 (which is 101 in binary) has a population count of 2.
Evil numbers are non-negative integers that have an even population count.
Odious numbers are positive integers that have an odd population count.
- Task
- 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 indexed).
- display the pop count of the 1st thirty powers of 3 (30, 31, 32, 33, 34, ∙∙∙ 329).
- 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
- The On-Line Encyclopedia of Integer Sequences: A000069 odious numbers.
- The On-Line Encyclopedia of Integer Sequences: A001969 evil numbers.
Ada
Specification 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
ALGOL 68
<lang algol68># returns the population count (number of bits on) of the non-negative #
- integer n #
PROC population count = ( LONG INT n )INT:
BEGIN LONG INT number := n; INT result := 0; WHILE number > 0 DO IF ODD number THEN result +:= 1 FI; number OVERAB 2 OD; result END # population # ;
- population count of 3^0, 3^1, 3*2, ..., 3^29 #
LONG INT power of three := 1; print( ( "3^x pop counts:" ) ); FOR power FROM 0 TO 29 DO
print( ( " ", whole( population count( power of three ), 0 ) ) ); power of three *:= 3
OD; print( ( newline ) );
- print the first thirty evil numbers (even population count) #
INT evil count := 0; print( ( "evil numbers :" ) ); FOR n FROM 0 WHILE evil count < 30 DO
IF NOT ODD population count( n ) THEN print( ( " ", whole( n, 0 ) ) ); evil count +:= 1 FI
OD; print( ( newline ) );
- print the first thirty odious numbers (odd population count) #
INT odious count := 0; print( ( "odious numbers:" ) ); FOR n WHILE odious count < 30 DO
IF ODD population count( n ) THEN print( ( " ", whole( n, 0 ) ) ); odious count +:= 1 FI
OD; print( ( newline ) ) </lang>
- Output:
3^x pop counts: 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
AppleScript
<lang AppleScript>-- popCount :: Int -> Int on popCount(n)
script bitSum on |λ|(a, x) a + (x as integer) end |λ| end script foldl(bitSum, 0, characters of showIntAtBase(n, 2))
end popCount
-- TEST -----------------------------------------------------------------------
on run
script powerOfThreePopCount on |λ|(x) popCount(3 ^ x) end |λ| end script script popCountisEven on |λ|(x) popCount(x) mod 2 = 0 end |λ| end script {popCounts:¬ map(powerOfThreePopCount, enumFromTo(0, 30)), evenThenOdd:¬ partition(popCountisEven, enumFromTo(0, 59))}
end run
-- GENERIC FUNCTIONS ----------------------------------------------------------
-- enumFromTo :: Int -> Int -> [Int] on enumFromTo(m, n)
if m > n then set d to -1 else set d to 1 end if set lst to {} repeat with i from m to n by d set end of lst to i end repeat return lst
end enumFromTo
-- foldl :: (a -> b -> a) -> a -> [b] -> a on foldl(f, startValue, xs)
tell mReturn(f) set v to startValue set lng to length of xs repeat with i from 1 to lng set v to |λ|(v, item i of xs, i, xs) end repeat return v end tell
end foldl
-- map :: (a -> b) -> [a] -> [b] on map(f, xs)
tell mReturn(f) set lng to length of xs set lst to {} repeat with i from 1 to lng set end of lst to |λ|(item i of xs, i, xs) end repeat return lst end tell
end map
-- Lift 2nd class handler function into 1st class script wrapper -- mReturn :: Handler -> Script on mReturn(f)
if class of f is script then f else script property |λ| : f end script end if
end mReturn
-- partition :: predicate -> List -> (Matches, nonMatches) -- partition :: (a -> Bool) -> [a] -> ([a], [a]) on partition(f, xs)
tell mReturn(f) set lst to {{}, {}} repeat with x in xs set v to contents of x set end of item ((|λ|(v) as integer) + 1) of lst to v end repeat end tell {item 2 of lst, item 1 of lst}
end partition
-- showIntAtBase :: Int -> Int -> String on showIntAtBase(n, base)
if base > 1 then if n > 0 then set m to n mod base set r to n - m if r > 0 then set prefix to showIntAtBase(r div base, base) else set prefix to "" end if if m < 10 then set baseCode to 48 -- "0" else set baseCode to 55 -- "A" - 10 end if prefix & character id (baseCode + m) else "0" end if else missing value end if
end showIntAtBase</lang>
- Output:
<lang AppleScript>{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, 25}, evenThenOdd: {{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}, {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>
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]
Elixir
<lang elixir>defmodule Population do
def count(n), do: count(<<n :: integer>>, 0)
defp count(<<>>, acc), do: acc
defp count(<<bit :: integer-1, rest :: bitstring>>, sum), do: count(rest, sum + bit) def evil?(n), do: n >= 0 and rem(count(n),2) == 0 def odious?(n), do: n >= 0 and rem(count(n),2) == 1
end
IO.puts "Population count of the first thirty powers of 3:" IO.inspect Stream.iterate(1, &(&1*3)) |> Enum.take(30) |> Enum.map(&Population.count(&1)) IO.puts "first thirty evil numbers:" IO.inspect Stream.iterate(0, &(&1+1)) |> Stream.filter(&Population.evil?(&1)) |> Enum.take(30) IO.puts "first thirty odious numbers:" IO.inspect Stream.iterate(0, &(&1+1)) |> Stream.filter(&Population.odious?(&1)) |> Enum.take(30)</lang>
- Output:
Population 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] 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]
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>
Forth
<lang Forth>: popcnt ( n -- u) 0 swap
BEGIN dup WHILE tuck 1 AND + swap 1 rshift REPEAT DROP ;
- odious? ( n -- t|f) popcnt 1 AND ;
- evil? ( n -- t|f) odious? 0= ;
CREATE A 30 ,
- task1 1 0 ." 3**i popcnt: "
BEGIN dup A @ < WHILE over popcnt . 1+ swap 3 * swap REPEAT DROP DROP CR ;
- task2 0 0 ." evil : "
BEGIN dup A @ < WHILE over evil? IF over . 1+ THEN swap 1+ swap REPEAT DROP DROP CR ;
- task3 0 0 ." odious : "
BEGIN dup A @ < WHILE over odious? IF over . 1+ THEN swap 1+ swap REPEAT DROP DROP CR ;
task1 task2 task3 BYE</lang>
- Output:
3**i popcnt: 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
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
Gambas
Click this link to run this code <lang gambas>Public Sub Main() Dim sEvil, sOdious As String 'To store the output for printing Evil and Odious Dim iCount, iEvil, iOdious As Integer 'Counters
Print "First 30 numbers ^3\t"; 'Print title
For iCount = 0 To 29 'Count 30 times
Print Len(Replace(Bin(3 ^ iCount), "0", ""));; 'Get the Bin of the number, take out the '0's and the remaining
Next 'length is the Population count e.g. 3^2=9, Bin=1001, remove '0's='11', length=2
iCount = 0 'Reset iCount
Repeat 'Repeat/Until loop
If Even(Len(Replace(Bin(iCount), "0", ""))) Then 'If (as above) the result is Even then sEvil &= Str(icount) & " " 'Add it to sEvil Inc iEvil 'Increase iEvil End If If Odd(Len(Replace(Bin(iCount), "0", ""))) Then 'If (as above) the result is Odd then sOdious &= Str(icount) & " " 'Add it to sOdious Inc iOdious 'Increase iOdious End If Inc iCount 'Increase iCount
Until iEvil = 30 And iOdious = 30 'Until both iEvil and iOdious = 30 then exit the loop
Print "\n1st 30 Evil numbers =\t" & sEvil 'Print Evil Print "1st 30 Odious numbers =\t" & sOdious 'Print Odious
End</lang> Output:
First 30 numbers ^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 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 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
Go
Standard Library
As of Go 1.9, this function is in the standard Library. <lang go>package main
import (
"fmt" "math/bits"
)
func main() {
fmt.Println("Pop counts, powers of 3:") n := uint64(1) // 3^0 for i := 0; i < 30; i++ { fmt.Printf("%d ", bits.OnesCount64(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 bits.OnesCount64(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
Implementation
Method of WP example popcount_3: <lang go>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)
}</lang> Method of WP example popcount_4: <lang go>func pop64(w uint64) (c int) {
for w != 0 { w &= w - 1 c++ } return
}</lang>
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]
Or, if we want to write our own popCount, perhaps something like:
<lang haskell>import Data.List (partition, unfoldr) import Data.Tuple (swap)
-- POPCOUNT ------------------------------------------------------------------- popCount :: Int -> Int popCount =
sum . unfoldr (\x -> if x > 0 then Just . swap $ quotRem x 2 else Nothing)
-- TEST ----------------------------------------------------------------------- main :: IO () main = do
print $ popCount . (3 ^) <$> [0 .. 29] let (evils, odii) = partition (even . popCount) [0 .. 59] mapM_ print [evils, odii]</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] [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] [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>countPopln=: +/"1@#: isOdd=: 1 = 2&| isEven=: 0 = 2&|</lang>
Task:
<lang J> countPopln 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{.(#~ isOdd@countPopln) 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{.(#~ isEven@countPopln) 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
JavaScript
ES6
<lang JavaScript>(() => {
// popCount :: Int -> Int const popCount = n => foldl( (a, x) => a + (x === '1' ? 1 : 0), 0, splitOn(, showIntAsBinary(n)) );
// GENERIC FUNCTIONS ------------------------------------------------------
// (++) :: [a] -> [a] -> [a] const append = (xs, ys) => xs.concat(ys);
// enumFromTo :: Int -> Int -> [Int] const enumFromTo = (m, n) => Array.from({ length: Math.floor(n - m) + 1 }, (_, i) => m + i);
// foldl :: (b -> a -> b) -> b -> [a] -> b const foldl = (f, a, xs) => xs.reduce(f, a);
// length :: [a] -> Int const length = xs => xs.length;
// map :: (a -> b) -> [a] -> [b] const map = (f, xs) => xs.map(f);
// raise :: Num -> Int -> Num const raise = Math.pow;
// showIntAsBinary :: Int -> String const showIntAsBinary = n => n.toString(2);
// splitOn :: String -> String -> [String] const splitOn = (cs, xs) => xs.split(cs);
// until :: (a -> Bool) -> (a -> a) -> a -> a const until = (p, f, x) => { let v = x; while (!p(v)) v = f(v); return v; }
// TEST -------------------------------------------------------------------
// { popCounts : [Int], evenThenOdd : ([Int], [Int]) } return { popCounts: map(x => popCount(raise(3, x)), enumFromTo(0, 30)), evenThenOdd: until( m => length(m.evenOdd[0]) >= 30 && length(m.evenOdd[1]) >= 30, m => ({ x: m.x + 1, evenOdd: popCount(m.x) % 2 === 0 ? ( [append(m.evenOdd[0], m.x), m.evenOdd[1]] ) : [m.evenOdd[0], append(m.evenOdd[1], m.x)] }), { x: 0, evenOdd: [ [], [] ] } ) .evenOdd };
})();</lang>
- Output:
<lang JavaScript>{"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, 25], "evenThenOdd":[ [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], [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>
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>
Kotlin
<lang scala>// version 1.0.6
fun popCount(n: Long) = when {
n < 0L -> throw IllegalArgumentException("n must be non-negative") else -> java.lang.Long.bitCount(n)
}
fun main(args: Array<String>) {
println("The population count of the first 30 powers of 3 are:") var pow3 = 1L for (i in 1..30) { print("${popCount(pow3)} ") pow3 *= 3L } println("\n") println("The first thirty evil numbers are:") var count = 0 var i = 0 while (true) { val pc = popCount(i.toLong()) if (pc % 2 == 0) { print("$i ") if (++count == 30) break } i++ } println("\n") println("The first thirty odious numbers are:") count = 0 i = 1 while (true) { val pc = popCount(i.toLong()) if (pc % 2 == 1) { print("$i ") if (++count == 30) break } i++ } println()
}</lang>
- Output:
The population count of the first 30 powers of 3 are: 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 are: 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 are: 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
Lua
<lang Lua>-- Take decimal number, return binary string function dec2bin (n)
local bin, bit = "" while n > 0 do bit = n % 2 n = math.floor(n / 2) bin = bit .. bin end return bin
end
-- Take decimal number, return population count as number function popCount (n)
local bin, count = dec2bin(n), 0 for pos = 1, bin:len() do if bin:sub(pos, pos) == "1" then count = count + 1 end end return count
end
-- Implement task requirements function firstThirty (mode)
local numStr, count, n, remainder = "", 0, 0 if mode == "Evil" then remainder = 0 else remainder = 1 end while count < 30 do if mode == "3^x" then numStr = numStr .. popCount(3 ^ count) .. " " count = count + 1 else if popCount(n) % 2 == remainder then numStr = numStr .. n .. " " count = count + 1 end n = n + 1 end end print(mode .. ":" , numStr)
end
-- Main procedure firstThirty("3^x") firstThirty("Evil") firstThirty("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
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}
Oforth
<lang oforth>: popcount(n)
0 while ( n ) [ n isOdd + n bitRight(1) ->n ] ;
- test
| i count |
30 seq map(#[ 3 swap 1- pow ]) map(#popcount) println 0 ->count 0 while( count 30 <> ) [ dup popcount isEven ifTrue: [ dup . count 1+ ->count ] 1+ ] drop printcr
0 ->count 0 while( count 30 <> ) [ dup popcount isOdd ifTrue: [ dup . count 1+ ->count ] 1+ ] drop ;</lang>
- Output:
>test [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] 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 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
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]
Pascal
Like Ada a unit is used. <lang pascal>unit popcount; {$IFDEF FPC}
{$MODE DELPHI} {$OPTIMIZATION ON,ASMCSE,CSE,PEEPHOLE} {$Smartlink OFF}
{$ENDIF}
interface
function popcnt(n:Uint64):integer;overload; function popcnt(n:Uint32):integer;overload; function popcnt(n:Uint16):integer;overload; function popcnt(n:Uint8):integer;overload;
implementation const //K1 = $0101010101010101;
K33 = $3333333333333333; K55 = $5555555555555555; KF1 = $0F0F0F0F0F0F0F0F; KF2 = $00FF00FF00FF00FF; KF4 = $0000FFFF0000FFFF; KF8 = $00000000FFFFFFFF;
{ function popcnt64(n:Uint64):integer; begin
n := n- (n shr 1) AND K55; n := (n AND K33)+ ((n shr 2) AND K33); n := (n + (n shr 4)) AND KF1; n := (n*k1) SHR 56; result := n;
end; } function popcnt(n:Uint64):integer;overload; // on Intel Haswell 2x faster for fpc 32-Bit begin
n := (n AND K55)+((n shr 1) AND K55); n := (n AND K33)+((n shr 2) AND K33); n := (n AND KF1)+((n shr 4) AND KF1); n := (n AND KF2)+((n shr 8) AND KF2); n := (n AND KF4)+((n shr 16) AND KF4); n := (n AND KF8)+ (n shr 32); result := n;
end;
function popcnt(n:Uint32):integer;overload; var
c,b : NativeUint;
begin
b := n; c := (b shr 1) AND NativeUint(K55); b := (b AND NativeUint(K55))+C; c := ((b shr 2) AND NativeUint(K33));b := (b AND NativeUint(K33))+C; c:= ((b shr 4) AND NativeUint(KF1)); b := (b AND NativeUint(KF1))+c; c := ((b shr 8) AND NativeUint(KF2));b := (b AND NativeUint(KF2))+c; c := b shr 16; b := (b AND NativeUint(KF4))+ C; result := b;
end;
function popcnt(n:Uint16):integer;overload; var
c,b : NativeUint;
begin
b := n; c := (b shr 1) AND NativeUint(K55); b := (b AND NativeUint(K55))+C; c :=((b shr 2) AND NativeUint(K33)); b := (b AND NativeUint(K33))+C; c:= ((b shr 4) AND NativeUint(KF1)); b := (b AND NativeUint(KF1))+c; c := b shr 8; b := (b AND NativeUint(KF2))+c; result := b;
end;
function popcnt(n:Uint8):integer;overload; var
c,b : NativeUint;
begin
b := n; c := (b shr 1) AND NativeUint(K55); b := (b AND NativeUint(K55))+C; c :=((b shr 2) AND NativeUint(K33));b := (b AND NativeUint(K33))+C; c:= b shr 4; result := (b AND NativeUint(KF1))+c;
end;
Begin End.</lang> The program <lang pascal>program pcntTest; uses
sysutils,popCount;
function Odious(n:Uint32):boolean;inline; Begin
Odious := boolean(PopCnt(n) AND 1)
end;
function EvilNumber(n:Uint32):boolean;inline; begin
EvilNumber := boolean(NOT(PopCnt(n)) AND 1);
end;
var
s : String; i : Uint64; k : LongWord;
Begin
s :='PopCnt 3^i :'; i:= 1; For k := 1 to 30 do Begin s := s+InttoStr(PopCnt(i)) +' '; i := 3*i; end; writeln(s);writeln;
s:='Evil numbers :';i := 0;k := 0; repeat IF EvilNumber(i) then Begin inc(k);s := s+InttoStr(i) +' '; end; inc(i); until k = 30; writeln(s);writeln;s:=;
s:='Odious numbers :';i := 0;k := 0; repeat IF Odious(i) then Begin inc(k);s := s+InttoStr(i) +' '; end; inc(i); until k = 30; writeln(s);
end.</lang>
- Output
PopCnt 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 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
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 three easily support bigints, the last 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 Math::BigInt; say 0 + (Math::BigInt->new(1234567)->as_bin() =~ tr/1//);
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>
Phix
<lang Phix>function pop_count(atom n)
if n<0 then ?9/0 end if integer res = 0 while n!=0 do res += and_bits(n,1) n = floor(n/2) end while return res
end function
sequence s = {} for i=0 to 29 do
s &= pop_count(power(3,i))
end for puts(1,"3^x pop_counts:") ?s
procedure eo(integer b0, string name)
integer k=0, l=1 while l<=30 do if and_bits(pop_count(k),1)=b0 then s[l] = k l += 1 end if k += 1 end while puts(1,name&" numbers:") ?s
end procedure eo(0," evil") eo(1,"odious")</lang>
- Output:
3^x pop_counts:{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}
PowerShell
<lang PowerShell> function pop-count($n) {
(([Convert]::ToString($n, 2)).toCharArray() | where {$_ -eq '1'}).count
} "pop_count 3^n: $(1..29 | foreach -Begin {$n = 1; (pop-count $n)} -Process {$n = 3*$n; (pop-count $n)} )" "even pop_count: $($m = $n = 0; while($m -lt 30) {if(0 -eq ((pop-count $n)%2)) {$m += 1; $n}; $n += 1} )" "odd pop_count: $($m = $n = 0; while($m -lt 30) {if(1 -eq ((pop-count $n)%2)) {$m += 1; $n}; $n += 1} )" </lang> Output:
pop_count 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 even pop_count: 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 odd pop_count: 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
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 decimal number, and */ /*───────────────────────── also generates a specific number of EVIL and ODIOUS numbers.*/ parse arg N B . /*get optional arguments from the C.L. */ if N== | N=="," then N=30 /*N not specified? Then use default. */ if B== | B=="," then B= 3 /*B " " " " " */ numeric digits 3000 /*be able to handle gihugeic numbers.*/ numeric digits max(20, length(B**N)) /*whittle the precision down to size.*/
/* [↑] a little calculation for sizing*/
$=; do j=0 for N /*generate N popCounts for some powers.*/
$=$ popCount(B**j) /*get the popCount for a power of B. */ end /*j*/ /* [↑] append popCount to the $ list. */ /* [↓] display popcounts of "3" powers*/
call showList 'popcounts of the powers of' B /*display the list with a header/title.*/
do j=0 until #==N /*generate N evil numbers. */ if popCount(j) // 2 then iterate /*if odd population count, skip it. */ #=#+1 /*bump the evil number counter. */ $=$ j /*append an evil number to a list.*/ end /*j*/ /* [↑] build a list of evil numbers. */ /* [↓] display the evil number 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, then skip. */ #=#+1 /*bump the odious number counter. */ $=$ j /*append an odious number to a list. */ end /*j*/ /* [↑] build a list of odious numbers.*/ /* [↓] display the odious number list.*/
call showList 'odious numbers' /*display the $ list with a header. */ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ d2b: return word( strip( x2b( d2x( arg(1) ) ), 'L', 0) 0, 1) /*dec ──► bin.*/ popCount: return length( space( translate( d2b(arg(1) ), , 0), 0) ) /*count ones. */ 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.digits(2).count(1) #pre Ruby 2.4: self.to_s(2).count("1") end def evil? self >= 0 && popcount.even? end def odious? self > 0 && popcount.odd? end
end
puts "Powers of 3:", (0...30).map{|n| (3**n).popcount}.join(' ') puts "Evil:" , 0.step.lazy.select(&:evil? ).first(30).join(' ') puts "Odious:", 0.step.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
Rust
<lang Rust> fn main() {
let mut num = 1u64; let mut vec = Vec::new(); for _ in 0..30 { vec.push(num.count_ones()); num *= 3; } println!("pop count of 3^0, 3^1 ... 3^29:\n{:?}",vec); let mut even = Vec::new(); let mut odd = Vec::new(); num = 1; while even.len() < 30 || odd.len() < 30 { match 0 == num.count_ones()%2 { true if even.len() < 30 => even.push(num), false if odd.len() < 30 => odd.push(num), _ => {} } num += 1; } println!("\nFirst 30 even pop count:\n{:?}",even); println!("\nFirst 30 odd pop count:\n{:?}",odd);
} </lang>
- Output:
pop count of 3^0, 3^1 ... 3^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] First 30 even pop count: [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, 60] First 30 odd pop count: [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
Sidef
<lang ruby>func population_count(n) { n.as_bin.count('1') } say "#{0..29 «**« 3 «call« population_count -> join(' ')}" var numbers = 60.of { |i|
[i, population_count(i)]
} say "Evil: #{numbers.grep{_[1] %% 2}.map{.first}.join(' ')}" say "Odious: #{numbers.grep{_[1] & 1}.map{.first}.join(' ')}"</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..].filter(30,fcn(n){ n.num1s.isEven }).concat(","));
// now, as an iterator aka lazy: println("odious: ",(0).walker(*).tweak( // 0,1,2,3,4... iterator
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