Convert a sequence of bits to a bit-string

mensanator at aol.com mensanator at aol.com
Sat Dec 15 12:42:06 EST 2007


On Dec 15, 10:39�am, te... at york.ac.uk wrote:
> First of all I'd like to thank you all for your advices. Before I check all
> your hints I want to clarify what I'm trying to do. The question says
> "write a function that takes a sequence of bits as an input and return how
> many 1s are in the sequence", nothing more.

Except that there is no such thing in Python
as there is no binary representation. You could
enter a sequence of characters, where each character
represents a bit, such as s='1111' for 15.

> This is quite simple for string
> inputs but tricky for "number inputs". I've notice that if I try to convert
> a number starting with 0 to a string using str(), then I take a string
> representing another number (probably converted to decimal). So what I want
> to do is to write a generic version of a function that takes as an input a
> sequence of 1s and 0s in any format.

That's probably not what you want. You don't want
to enter 1's and 0's in any format, you want to
accept a number in any format. Remember, the format
does not change the number (assuming you always use
the correct format representation).

So if the input is s=017 (octal), the number
is fifteen. If s=0xf (hexadecimal), the number
is fifteen. If s=15 (decimal), the number is
fifteen.

Once you've got that straight, you can calculate
the base 2 representation of fifteen and count
the ones.

> The only way I can think to achieve
> that is by converting the "number inputs" to a string and then using the
> count() function.

Do you know how base conversion is done manually?

In base 2, each bit represents a power of 2, and
there are only two possibilities for each digit,
0 and 1. So, in base 2, the digit positions
are

... 2**7 2**6 2**5 2**4 2**3 2**2 2**1 2**0
    128  64   32   16   8    4    2    1

Now, for fifteen, what's the largest position
that doesn't exceed 15? The fourth (counting
from the right). Therefore, there's a 1 bit
in position four and all higher positions
would be 0. At this point, we have '1???'.

To get the next lower position, subtract 8
from fifteen, leaving seven. Now repeat
until you fill all positions, eventually
reaching '1111'.

But, if the highest position that doesn't
exceed skips some positions, then those
positions have '0'.

So for nine, the highest position is still
the fourth, giving us '1???'. But after
subtracting eight, we're left with one.

But the highest position not exceeding one
is the first, giving us '1??1'. We skipped
positions 2 & 3, so they must be '0' making
nine '1001' in base 2.

Now all you have to do is count the 1's.

However, if doing

> Thomas




More information about the Python-list mailing list