Population count: Difference between revisions
(→{{header|Perl}}: comment about infinite lists) |
m (→{{header|Perl}}: plural) |
||
Line 359: | Line 359: | ||
{{trans|Perl 6}} |
{{trans|Perl 6}} |
||
We'll emulate infinite lists with |
We'll emulate infinite lists with closures. |
||
<lang perl>use strict; |
<lang perl>use strict; |
Revision as of 10:07, 18 March 2014
The population count (also known as pop count, sideways sum, and Hamming weight) is the number of 1's (ones) in the binary representation of an non-negative integer.
- 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).
- 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.
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
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
D
<lang d>void main() {
import std.stdio, std.algorithm, std.range, core.bitop;
const pCount = (ulong n) => popcnt(cast(uint)n) + popcnt(n >> 32); uint.max.iota.map!(i => pCount(3L ^^ i)).take(30).writeln; uint.max.iota.filter!(i => pCount(i) % 2 == 0).take(30).writeln; uint.max.iota.filter!(i => pCount(i) % 2).take(30).writeln;
}</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]
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("~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(). [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>
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() {
n := uint64(1) // 3^0 for i := 0; i < 30; i++ { fmt.Printf("%d ", pop64(n)) n *= 3 } fmt.Println() 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() for _, n := range od { fmt.Printf("%d ", n) } fmt.Println()
}</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
Haskell
<lang haskell>import Data.Bits (popCount)
main :: IO () main = do
print $ take 30 $ map popCount $ iterate (* 3) (1 :: Integer) print $ take 30 $ filter (even . popCount) ([0..] :: [Integer]) print $ take 30 $ filter (odd . popCount) ([0..] :: [Integer])</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>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
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
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
PARI/GP
<lang parigp>vector(30,n,hammingweight(3^(n-1))) od=select(n->hammingweight(n)%2,[1..100]); ev=setminus([1..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 = [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] %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
Perl 6
<lang perl6>sub population-count(Int $n where * >= 0) { [+] $n.base(2).comb }
say map &population-count, 3 «**« ^30; say (grep { population-count($_) %% 2 }, 0 .. *)[^30]; say (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 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
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>
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 'powers of' B /*display the list with a header.*/
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 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
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