Population count: Difference between revisions
m
typo
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
Not a robot (talk | contribs) m (typo) |
||
| (21 intermediate revisions by 14 users not shown) | |||
Line 39:
{{trans|Python}}
<syntaxhighlight lang="11l">
[Int] evil, odious
V i = 0
L evil.len < 30 | odious.len < 30
V p = bits:popcount(i)
I (p % 2) != 0
odious.append(i)
Line 368 ⟶ 365:
00 03 05 06 09 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
01 02 04 07 08 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>
=={{header|ABC}}==
<syntaxhighlight lang="abc">HOW TO RETURN popcount n:
IF n=0: RETURN 0
RETURN (n mod 2) + popcount (floor (n/2))
HOW TO REPORT evil n:
REPORT (popcount n) mod 2 = 0
HOW TO REPORT odious n:
REPORT (popcount n) mod 2 = 1
FOR i IN {0..29}: WRITE popcount (3 ** i)
WRITE /
PUT {} IN evilnums
PUT {} IN odiousnums
FOR n IN {0..59}:
SELECT:
evil n: INSERT n IN evilnums
odious n: INSERT n IN odiousnums
FOR i IN {1..30}: WRITE evilnums item i
WRITE /
FOR i IN {1..30}: WRITE odiousnums item i
WRITE /</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Ada}}==
Line 979 ⟶ 1,007:
</pre>
=={{header|
==={{header|BASIC256}}===
{{trans|Yabasic}}
<syntaxhighlight lang="basic256">print "Pop cont (3^x): ";
Line 1,016 ⟶ 1,045:
return popul
end function</syntaxhighlight>
==={{header|Run BASIC}}===
<syntaxhighlight lang="vb">function tobin$(num)
bin$ = ""
if num = 0 then bin$ = "0"
while num >= 1
num = num / 2
X$ = str$(num)
D$ = "": F$ = ""
for i = 1 to len(X$)
L$ = mid$(X$, i, 1)
if L$ <> "." then
D$ = D$ + L$
else
F$ = F$ + right$(X$, len(X$) - i)
exit for
end if
next i
if F$ = "" then B$ = "0" else B$ = "1"
bin$ = bin$ + B$
num = val(D$)
wend
B$ = ""
for i = len(bin$) to 1 step -1
B$ = B$ + mid$(bin$, i, 1)
next i
tobin$ = B$
end function
function population(number)
popul = 0
'digito$ = tobin$(number)
'print tobin$(number)
for i = 1 to len(tobin$(number))
popul = popul + val(mid$(tobin$(number), i, 1))
next i
population = popul
end function
sub evilodious limit, tipo
i = 0
cont = 0
while 1
eo = (population(i) mod 2)
if (tipo and eo = 1) or ((not(tipo) and not(eo)) = 1) then
cont = cont + 1: print i; " ";
end if
i = i + 1
if cont = limit then exit while
wend
end sub
print "Pop cont (3^x): ";
for i = 0 to 14
print population(3 ^ i); " ";
next i
print
print "Evil numbers: ";
call evilodious 15, 0
print
print "Odious numbers: ";
call evilodious 15, 1
end</syntaxhighlight>
=={{header|BCPL}}==
Line 1,642 ⟶ 1,739:
</syntaxhighlight>
=={{header|EasyLang}}==
<syntaxhighlight>
func popcnt x .
while x > 0
r += x mod 2
x = x div 2
.
return r
.
proc show3 . .
write "3^n:"
bb = 1
for i = 1 to 30
write " " & popcnt bb
bb *= 3
.
print ""
.
proc show s$ x . .
write s$
while n < 30
if popcnt i mod 2 = x
n += 1
write " " & i
.
i += 1
.
print ""
.
show3
show "evil:" 0
show "odious:" 1
</syntaxhighlight>
=={{header|Elixir}}==
Line 1,938 ⟶ 2,070:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Population_count}}
'''Solution'''
Fōrmulæ has an integrated expression BitCount that counts the number of 1's of the binary representation of the number.
However, a function can also be written, as follows:
[[File:Fōrmulæ - Population count 01.png]]
'''Case 1. Display the pop count of the 1st thirty powers of 3'''
[[File:Fōrmulæ - Population count 02.png]]
[[File:Fōrmulæ - Population count 03.png]]
'''Case 2. Display the 1st thirty evil numbers'''
We need first a function to calculate the first numbers whose population count satisfies a given condition, passed as a lambda expression:
[[File:Fōrmulæ - Population count 04.png]]
[[File:Fōrmulæ - Population count 05.png]]
[[File:Fōrmulæ - Population count 06.png]]
'''Case 3. Display the 1st thirty odious numbers'''
[[File:Fōrmulæ - Population count 07.png]]
[[File:Fōrmulæ - Population count 08.png]]
=={{Header|FreeBASIC}}==
Line 1,989 ⟶ 2,147:
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>
=={{Header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
_limit = 30
local fn Population( x as long ) as long
long q, r, y = 0
while ( x > 0 )
q = int( x / 2 )
r = x - q * 2
if r == 1 then y++
x = q
wend
end fn = y
void local fn EvilOdious
long i = 0, k, ee = 0, eo = 0
long type(_limit - 1), evil(_limit - 1), odious(_limit - 1)
Str255 typeStr, evilStr, odiousStr
while ( ( ee < _limit ) or ( eo < _limit ) )
if i < _limit then type(i) = fn Population(3^i)
k = fn Population(i)
if k mod 2 == 0 and ee < _limit then evil(ee) = i : ee++
if k mod 2 == 1 and eo < _limit then odious(eo) = i : eo++
i++
wend
typeStr = "" : evilStr = "" : odiousStr = ""
for i = 0 to _limit - 1
typeStr = typeStr + str$( type(i) ) + " "
evilStr = evilStr + str$( evil(i) ) + " "
odiousStr = odiousStr + str$( odious(i) ) + " "
next
print typeStr : print evilStr : print odiousStr
end fn
fn EvilOdious
HandleEvent
</syntaxhighlight>
{{output}}
<pre>
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
</pre>
=={{header|Gambas}}==
Line 2,577 ⟶ 2,785:
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</pre>
=={{header|M2000 Interpreter}}==
=====Using just Count() and loops=====
<syntaxhighlight lang="m2000 interpreter">
Module Population_count{
Function Count(x as long long) {
integer Count
long long m=x
m|div 0x1_0000_0000&&
x|mod 0x1_0000_0000&&
While x<>0&
x=Binary.And(X, X-1&&)
Count++
End While
x=m
While x<>0&
x=Binary.And(X, X-1&&)
Count++
End While
=Count
}
long long i, b=3
stack new {
for i=0 to 29
Data count(b^i)
next
print "3^x population:", array([])#str$()
i=0: b=0
while i<30
if Count(b) mod 2=0 then data b:i++
b++
end while
print "evil numbers:", array([])#str$()
i=0: b=0
while i<30
if Count(b) mod 2=1 then data b:i++
b++
end while
print "odious numbers:", array([])#str$()
}
}
Population_count
</syntaxhighlight>
=====Using Generators=====
<syntaxhighlight lang="m2000 interpreter">
Module Population_count{
Count=lambda (x as long long)->{
integer Count
long long m=x
m|div 0x1_0000_0000&&
x|mod 0x1_0000_0000&&
While x<>0&
x=Binary.And(X, X-1&&)
Count++
End While
x=m
While x<>0&
x=Binary.And(X, X-1&&)
Count++
End While
=Count
}
series3pow=lambda Count, i=0&& -> {
=count(3&&^i):i++
}
seriesEvil=lambda Count, i=0&&-> {
while Count(i) mod 2=1{i++}
=i:i++
}
seriesOdious=lambda Count, i=0&&-> {
while Count(i) mod 2=0{i++}
=i:i++
}
Dim a(30)<<series3pow()
print "3^x population:", a()#str$()
Dim a(30)<<seriesEvil()
print "evil numbers:", a()#str$()
Dim a(30)<<seriesOdious()
print "odious numbers:", a()#str$()
}
Population_count
</syntaxhighlight>
{{out}}
<pre>
3^x population: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
</pre>
=={{header|MAD}}==
Line 2,776 ⟶ 3,075:
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)
</pre>
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout (lay (map (show . take 30) [powers_of_3, evil, odious]))]
powers_of_3 :: [num]
powers_of_3 = map (popcount . (3^)) [0..]
evil :: [num]
evil = filter f [0..] where f n = popcount n mod 2 = 0
odious :: [num]
odious = filter f [0..] where f n = popcount n mod 2 = 1
popcount :: num -> num
popcount 0 = 0
popcount n = n mod 2 + popcount (n div 2)</syntaxhighlight>
{{out}}
<pre>[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]</pre>
=={{header|Nim}}==
Line 2,832 ⟶ 3,152:
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</pre>
=={{header|OCaml}}==
<syntaxhighlight lang="ocaml">let popcount n =
let rec aux acc = function
| 0 -> acc
| x -> aux (succ acc) (x land pred x)
in
aux 0 n
let is_parity p x =
p = 1 land popcount x
(* test code *)
let powers3_seq () =
Seq.unfold (fun x -> Some (popcount x, x * 3)) 1
let parity_seq p =
Seq.(filter (is_parity p) (ints 0))
let print_seq_30 s =
Seq.(s |> take 30 |> map string_of_int)
|> List.of_seq |> String.concat " " |> print_endline
let () = print_seq_30 (powers3_seq ())
let () = print_seq_30 (parity_seq 0)
let () = print_seq_30 (parity_seq 1)</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Oforth}}==
Line 2,853 ⟶ 3,206:
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
</pre>
=={{header|Ol}}==
<syntaxhighlight lang="scheme">
(define (popcount n)
(let loop ((n n) (c 0))
(if (= n 0)
c
(loop (>> n 1)
(if (eq? (band n 1) 0) c (+ c 1))))))
(print (popcount 31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253))
(define thirty 30)
(display "popcount:")
(for-each (lambda (i)
(display " ")
(display (popcount (expt 3 i))))
(iota thirty 0))
(print)
(define (evenodd name test)
(display name) (display ":")
(for-each (lambda (i)
(display " ")
(display i))
(reverse
(let loop ((n 0) (i 0) (out '()))
(if (= i thirty)
out
(if (test (popcount n))
(loop (+ n 1) (+ i 1) (cons n out))
(loop (+ n 1) i out))))))
(print))
(evenodd "evil" even?)
(evenodd "odius" odd?)
</syntaxhighlight>
{{out}}
<pre>
159
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
odius: 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>
Line 3,070 ⟶ 3,468:
=={{header|Phix}}==
As of 1.0.2 there is a builtin count_bits(), and also mpz_popcount(), both of which match the results from pop_count() below.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 3,596 ⟶ 3,995:
$c;
}</syntaxhighlight>
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
= <Prout <Gen 30 All Pow3 (1)>>
<Prout <Gen 30 Evil Iota (0)>>
<Prout <Gen 30 Odious Iota (0)>>;
};
Gen {
0 s.Fil s.Gen (s.State) = ;
s.N s.Fil s.Gen (s.State),
<Mu s.Gen s.State>: (s.Next) s.Item,
<Mu s.Fil s.Item>: {
T = s.Item <Gen <- s.N 1> s.Fil s.Gen (s.Next)>;
F = <Gen s.N s.Fil s.Gen (s.Next)>;
};
};
Popcount {
0 = 0;
s.N, <Divmod s.N 2>: (s.R) s.B = <+ s.B <Popcount s.R>>;
};
Pow3 {
s.N = (<* 3 s.N>) <Popcount s.N>;
};
Evil {
s.N, <Mod <Popcount s.N> 2>: {
0 = T;
1 = F;
};
};
Odious {
s.N, <Mod <Popcount s.N> 2>: {
0 = F;
1 = T;
};
};
All { s.X = T; }
Iota { s.N = (<+ 1 s.N>) s.N; }</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|REXX}}==
Line 3,687 ⟶ 4,133:
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]</pre>
=={{header|RPL}}==
{{Trans|Forth}}
≪ # 0b SWAP
'''WHILE''' DUP # 0b ≠ '''REPEAT'''
DUP # 1b AND ROT + SWAP SR '''END'''
DROP B→R
≫ ''''POPCT'''' STO
≪ '''POPCT''' 2 MOD
≫ ‘'''ODUS?'''’ STO
≪ '''ODUS?''' NOT
≫ ‘'''EVIL?'''’ STO
≪ → n
≪ { } # 1b 1 n START
DUP '''POPCT''' ROT SWAP + SWAP 3 * NEXT DROP
{ } # 0b WHILE OVER SIZE n < REPEAT
IF DUP '''EVIL?''' THEN SWAP OVER B→R + SWAP END 1 + END DROP
{ } # 0b WHILE OVER SIZE n < REPEAT
IF DUP '''ODUS?''' THEN SWAP OVER B→R + SWAP END 1 + END DROP
≫ ≫ ‘TASK’ STO
30 TASK
{{out}}
<pre>
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 }
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 }
1: { 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>
=={{header|Ruby}}==
Line 3,817 ⟶ 4,294:
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 </pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program population_count;
print([popcount(3**n) : n in [0..29]]);
print([n : n in [0..59] | evil n]);
print([n : n in [0..59] | odious n]);
op evil(n);
return even popcount n;
end op;
op odious(n);
return odd popcount n;
end op;
op popcount(n);
return +/[[n mod 2, n div:=2](1) : until n=0];
end op;
end program;</syntaxhighlight>
{{out}}
<pre>[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]</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func population_count(n) { n.as_bin.count('1') }
Line 4,152 ⟶ 4,651:
{{libheader|Wren-fmt}}
The first part is slightly awkward for Wren as 'native' bit-wise operations are limited to unsigned 32-bit integers and 3^21 exceeds this limit. We therefore need to switch to BigInts just before that point to process the remaining powers.
<syntaxhighlight lang="
import "./fmt" for Fmt
var popCount = Fn.new { |n|
Line 4,199 ⟶ 4,698:
The first 30 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
</pre>
=={{header|XPL0}}==
Double precision floating point numbers are used because XPL0's 32-bit
integers don't have sufficient precision to reach 3^29. Double precision
has a 53-bit mantissa that can represent integers up to 2^53, which is
approximately 9.0e15 or approximately 3^33, which is sufficient.
<syntaxhighlight lang "XPL0">func PopCnt(N); \Return count of 1s in binary representation of N
real N; int C;
[C:= 0;
while N >= 0.5 do
[if fix(Mod(N, 2.)) = 1 then C:= C+1;
N:= Floor(N/2.);
];
return C;
];
proc Show30(LSb); \Display 30 numbers with even or odd population count
int LSb, C; real N; \Least Significant bit determines even or odd
[N:= 0.; C:= 0;
repeat if (PopCnt(N)&1) = LSb then
[RlOut(0, N); C:= C+1];
N:= N+1.;
until C >= 30;
CrLf(0);
];
real N; int P;
[Format(3, 0);
Text(0, "Pow 3: ");
N:= 1.;
for P:= 0 to 29 do
[RlOut(0, float(PopCnt(N))); N:= N*3.];
CrLf(0);
Text(0, "Evil: "); Show30(0);
Text(0, "Odious:"); Show30(1);
]</syntaxhighlight>
{{out}}
<pre>
Pow 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
</pre>
| |||