0

Given a sequence of zeros and ones, e.g., 

1101110

I would like to sum all the elements of the sequence, and write the result in base 2, by using only logical operations between 0s and 1s. In this example, the sum is equal to 5, which in base 2 reads

101

and which is the desired result.

I know a simple way of achieving this, which consists in

  1. writing zero in base 2: 000
  2. adding to it the first bit in the sequence, i.e. 1, and obtain 001. This can be done with a XOR operation.
  3. adding the second bit to 001, and obtain 010, with a XOR operation and an AND operation to compute the carry.
  4. proceed in the same way for the remaining bits.

I suspect that this method is far from being optimal in terms of number of operations. Do you guys know a more efficient method?

James
  • 383
  • 1
  • 4
  • 15
  • The optimal solution in terms of number of operations would just look up the answer in a table. In other words, it seems like you're putting arbitrary restrictions on the solution, which make the solution inefficient by definition. So it's not clear what you're actually trying to accomplish. – user3386109 Oct 11 '18 at 20:52
  • Have a look at this [related question](https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer). – Axel Kemper Oct 11 '18 at 20:58
  • ahh I am guessing this is bitwise homework programming in machine code? that is why the you can use only logical operations? If so then you are stuck using XOR and AND functions to figure it out programmatically. and you should already know the method of turning a base 10 number into a base 2 as you showed in your question, – David Coler Oct 11 '18 at 21:06
  • 3
    This is a "population count" operation, and there are [many well-known tricks to doing it in a short sequence of simple bitwise operations and additions](https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive), if your platform doesn't provide a popcount instruction. Naturally you can build addition from bitwise operations as well. – Ben Voigt Oct 11 '18 at 21:20
  • It sounds like you are trying to replicate with software what is normally done in hardware. Is there a reason why you are restricting yourself to strictly manipulations of only one bit at a time? Even modern hardware description languages give you more control than this. Let your hardware deal with the low level stuff and just do math on machine words – HackerBoss Oct 13 '18 at 17:35
  • @HackerBoss I can manipulate only one bit at a time, because I intend to make multiple bitwise operations simultaneously. In the example that I gave above, the sequence `1101110' should be seen as a sequence a[0], a[1], ... , a[6] of 7 64-bit integers, where the i-th bit of a[0] is equal to 1, the i-th bit of a[1] is equal to 1, the i-th bit of a[2] is equal to 0, etc... I want to count the number of set bits, and write the result in binary form, in a sequence of 64-bit integers A[0],...A[3]. As a result, the i-th bit of A[0] will be 1, the i-th bit of A[1] = 0, and the i-th bit of A[2] = 1. – James Oct 15 '18 at 14:06

0 Answers0