Can Sup Forums find the number of binary 1s in a number without using loops or recursions

Can Sup Forums find the number of binary 1s in a number without using loops or recursions.
Brotip: you can't

Other urls found in this thread:

felixcloutier.com/x86/POPCNT.html
en.wikipedia.org/wiki/Hamming_weight
web.mit.edu/humor/Computers/real.programmers
twitter.com/AnonBabble

for help with homework

This isn't homework tho

Not doing your job/homework kid.

You are not smart to show that you can walk without your legs

This is a standard way to weed out stackoverflow copypasters.

So you are weeding out people that don't walk on their hands?

int-- hey wait a minute no

Well, if we know the representation format of the number (number of bits), it's easy to do it in O(1).
Is there a nicer way I'm missing?

popcnt

sure you can, just look at implementation in standard library of any language
#include
#include

const uint8_t pop8tab[256] = {
0x00,0x01,0x01,0x02,0x01,0x02,0x02,0x03,0x01,0x02,0x02,0x03,0x02,0x03,0x03,0x04,
0x01,0x02,0x02,0x03,0x02,0x03,0x03,0x04,0x02,0x03,0x03,0x04,0x03,0x04,0x04,0x05,
0x01,0x02,0x02,0x03,0x02,0x03,0x03,0x04,0x02,0x03,0x03,0x04,0x03,0x04,0x04,0x05,
0x02,0x03,0x03,0x04,0x03,0x04,0x04,0x05,0x03,0x04,0x04,0x05,0x04,0x05,0x05,0x06,
0x01,0x02,0x02,0x03,0x02,0x03,0x03,0x04,0x02,0x03,0x03,0x04,0x03,0x04,0x04,0x05,
0x02,0x03,0x03,0x04,0x03,0x04,0x04,0x05,0x03,0x04,0x04,0x05,0x04,0x05,0x05,0x06,
0x02,0x03,0x03,0x04,0x03,0x04,0x04,0x05,0x03,0x04,0x04,0x05,0x04,0x05,0x05,0x06,
0x03,0x04,0x04,0x05,0x04,0x05,0x05,0x06,0x04,0x05,0x05,0x06,0x05,0x06,0x06,0x07,
0x01,0x02,0x02,0x03,0x02,0x03,0x03,0x04,0x02,0x03,0x03,0x04,0x03,0x04,0x04,0x05,
0x02,0x03,0x03,0x04,0x03,0x04,0x04,0x05,0x03,0x04,0x04,0x05,0x04,0x05,0x05,0x06,
0x02,0x03,0x03,0x04,0x03,0x04,0x04,0x05,0x03,0x04,0x04,0x05,0x04,0x05,0x05,0x06,
0x03,0x04,0x04,0x05,0x04,0x05,0x05,0x06,0x04,0x05,0x05,0x06,0x05,0x06,0x06,0x07,
0x02,0x03,0x03,0x04,0x03,0x04,0x04,0x05,0x03,0x04,0x04,0x05,0x04,0x05,0x05,0x06,
0x03,0x04,0x04,0x05,0x04,0x05,0x05,0x06,0x04,0x05,0x05,0x06,0x05,0x06,0x06,0x07,
0x03,0x04,0x04,0x05,0x04,0x05,0x05,0x06,0x04,0x05,0x05,0x06,0x05,0x06,0x06,0x07,
0x04,0x05,0x05,0x06,0x05,0x06,0x06,0x07,0x05,0x06,0x06,0x07,0x06,0x07,0x07,0x08,
};

int
count_ones(uint32_t x)
{
return (int)(pop8tab[x] + pop8tab[x&0xff] + pop8tab[x&0xff] + pop8tab[x&0xff]);
}

int
main(int argc, char **argv)
{
uint32_t x;
for (int i = 1; i < argc; i++) {
if (sscanf(argv[i], "%u", &x) != 1) {
fprintf(stderr, "error parsing %s\n", argv[i]);
continue;
}
int ones = count_ones(x);
printf("%u has %d ones\n", x, ones);
}
return 0;
}

Big brain Matlab user here:
sum(bitget(num,1:64))

Works for 64 bit number.

Single instruction on most CPUs
felixcloutier.com/x86/POPCNT.html

easy
main(int argc, char **argv)
{
unsigned int x;
for (int i = 1; i < argc; i++) {
if (sscanf(argv[i], "%u", &x) != 1) {
fprintf(stderr, "error parsing %s\n", argv[i]);
continue;
}
int ones = __builtin_popcount(x);
printf("%u has %d ones\n", x, ones);
}
return 0;
}

also en.wikipedia.org/wiki/Hamming_weight

Simple:
15.toBinaryString.count(x=>x=='1')
Some low level microoptimizer will probably complain this uses a loop somewhere in the standard lib or compiler or the kernel it runs on, but *I* did not.

>no loops
>for statement
>iteration over an array

wew

There is no for statement or iteration in this code.

sum hides a loop

get_flipped:
popcnt %rdi, %rax
ret

how is iterating over a collection not a loop?

Doesn't work for arbitrary large integer sizes.

then you popcnt each fucking byte and sum them in a loop

I feel like there's a way to do this by comparing the characteristic and mantissa of the log2 of the number

>sum them in a loop
>loop

Yes i will say it again: LOOP

Not part of that line of code, no.

Of course it's pretty much guaranteed that the standard library that implements this function as well as compiler that compiles the code and the JVM / OS / kernel / hardware / firmware it runs on will do both recursions and loops.
But not this snippet of code itself.

>OP says loops
>everyone uses loops
>reference implementations use loops

cmon guys this is just b8

Also I'm a level 8 matlab indexing guru and cna tell you that single liner matlab calls use a shit ton of loops in the compiled C libraries.

If you want to run a program without any loops go to processes in task manager, right click on "System" and end the process. This lets the computer run however no code will be executed. It's more amusing to freeze the process rather than kill it (windows 7 only). This stopped being allowed in windows 8.

bin(number)[2:].count('1')

I dun goofed
int hakmem169_32(unsigned int x) {
x = x - ((x >> 1) & 033333333333)
- ((x >> 2) & 011111111111);
x = (x + (x >> 3)) & 030707070707 ;
return x % 63; /* casting out 63 */
}

A stupid question has a stupid answer (third fucking try).

// no loop 8-bit integer binary digit counter
unsigned int x;
x = 0;
if mod(arg,2) > 0
x++;
end
if mod(arg,4) > 0
x++;
end
if mod(arg,8) > 0
x++;
end
if mod(arg,16) > 0
x++;
end
if mod(arg,32) > 0
x++;
end
if mod(arg,64) > 0
x++;
end
if mod(arg,128) > 0
x++;
end
return x;

what weird ass programming language is this shit?

It isn't a language. Funny how everyone can still understand it though. Hmm it's almost like using a specific language is dumb.

this algo is completely wrong

shython

>Can Sup Forums find the number of binary 1s in a number without using loops or recursions.
You never said I had to do it in code.
I set Windows calculator to Programmer view, and count the number of 1s in the decimal-to-binary conversion.

Can you, OP? How do I know it's not impossible?

std::sstream ss;
ss

x = 0;
if mod(arg,2) > 0
x = x + 1;
end
if mod(arg,4) > 1
x = x + 1;
end
if mod(arg,8) > 3
x = x + 1;
end
if mod(arg,16) > 7
x = x + 1;
end
if mod(arg,32) > 15
x = x + 1;
end
if mod(arg,64) > 31
x = x + 1;
end
if mod(arg,128) > 63
x = x + 1;
end
if arg > 127
x = x + 1;
end

count(z) = (z AND 1) + count(z/2)

and now your homework: translate this end-recursion into something that doesn't use it.

...

Precalculated table.

You are the reason 16 GB of memory is insufficient.

I just puked

:^)

OP pic shows only 8 bits. 256 entries is nothing.

why would you ever need this information to begin with

Scope matters. Increasing your memory footprint by a kilobyte doesn't matter. Increasing your memory footprint by 10000% does.

Ask their professor.

Then how would you do it without using loops nor recursions?
Tables are much faster than testing every individual bit.

Test each individual bit. Playing the memory juggle incurs a much larger performance penalty than spending 20x more cycles on the calculation. That's why loops are used instead of tables. Tables are only useful in video and embedded applications. Traditional computers are memory starved.

Neither does the processor. Your point?

num & 1 + num & 2 + .... + num & 128

Are you fucking retarded?
A 256 entry lookup table is enough even for 64bit values.
Though a 65536 entry lookup table wouldn't hurt either.

usize popcnt(u8 x) {
return tb[x];
}

usize popcnt(u16 x) {
auto p = reinterpret_cast(&x);
return popcnt(p[0]) + popcnt(p[1]);
}

usize popcnt(u32 x) {
auto p = reinterpret_cast(&x);
return popcnt(p[0]) + popcnt(p[1]);
}

usize popcnt(u64 x) {
auto p = reinterpret_cast(&x);
return popcnt(p[0]) + popcnt(p[1]);
}

Yeah and you're going to load up a new instance of that in memory every time your function is called? What if you call it a million times a second? Did you not register the literal first word in that post?

Are you fucking braindead? Do you not know what a static variable is?

Pshaw. 8 bits takes 256 bytes, 16 takes only 65k, and if you want to do 32 or 64 bits, just use the 16-bit table two to four times.

Alright then faggot, give me some realizable HDL for an ALU with arbratrarily large word size.

if mod(arg,2) > 0
x++;
end
if mod(arg,4) > 0
x++;
end

pajeet indentation / 10

Or you, you know, you could just make it a 1 bit table and do the calculation in a loop so you're not wasting cache. Benchmark it yourself.

+/@:(2&#.^:_1)

C'mon user, aren't these challenges supposed to be hard? :^)

redundant and verbose / 10
14.toBinaryString count {_=='1'}

What the fuck am I looking at here? I want to understand this.

Not possible unless the size of your numbers is bounded

+/⊥⍣¯1

Or 2∘(+/⊥⍣¯1) I guess

print(sum(map(int, list('{0:b}'.format(37)))))

Replace 37 with custom input

pythonlets will actually defend this

Because this >+/@:(2&#.^:_1)
Is better right?

You fat nerds never cease to amuse me

>muh false dichotomy
oh you adorable little scamp
>python
print(sum(map(int, list('{0:b}'.format(37)))))

>less garbage languages
37.toBinaryString count {_=='1'}

PajeetMySonYouMustPooInTheCamelCase()

ran out of arguments that quickly, huh?
guess the things they say about Python "koders" really are true

>Not objecting to subjective preference means having no arguments
I'll let 100% of the scientific community decide whether Python is shit, thanks

guess PHP is a really great language too, with such a large community using it too, eh?

I made my first webpage using PHP. I think it's great.

popcnt eax, edi
ret

bin(37).count('1')

now this is more like it

What is 1s?

An analogue computer could

x=0
if(y >= 128) { y -=128; x++}
if(y >= 64) { y -=64; x++}
if(y >= 32) { y -=32; x++}
if(y >= 16) { y -=16; x++}
if(y >= 8) { y -=8; x++}
if(y >= 4) { y -=4; x++}
if(y >= 2) { y -=2; x++}
if(y) { x++}

sum(filter(int, bin(num)))

>sum(filter(int, bin(37)))
Traceback (most recent call last):
File "", line 1, in
ValueError: invalid literal for int() with base 10: 'b'

Why even use sum if you use filter?
You can just use len then.

>Scientific community == Poo programmers
LMAO

import binaryOnes;
binaryOnes.count(x);

int result = strtol(input, NULL, 2);

And fuck your gay shit

>unironically thinks scientists know anything about code quality
ho ho ho

FYI, a variant of this technique was used in the early 1980s by Richard James aka Aphex Twin to write an electronic piano program for the ZX81, a machine with no sound circuitry whatsoever.

In the ZX81, the Z80 CPU directly generates the television signal. By writing precisely timed BASIC code you can fuck up the TV signal just enough for the Cathode Ray Tube to itself produce sound.

In those days, programmers were real men ;)

As far as I know:
protip: this is right.
Answer: The max. power of loop/recursion languages is equivalent to the max.power of the language language of a Turing Machine.

For this problem, you'd need something that can count. How long? until n.
Need a TM or similar for that.

>programmers were real men
web.mit.edu/humor/Computers/real.programmers

return __builtin_popcount(num);

>__builtin_popcount
and longs?

__builtin_popcountll

nigger

Wonderful

So what's the purpose of this thread

smugposting around fizzbuzzery

...

unrolled loop