0

Hi so I need to create a program that will save the amount of on bits in ax to bx. I tried using SHR and SHL and it didnt wokred so well. If you can show me how can I check that using shr and shl I will be greatfull. Thanks

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
SkyBear
  • 3
  • 5
  • This operation is called the *population count.* What architecture are you programming for? It looks like some sort of x86 processor. Modern x86 processors have the `popcnt` instruction to compute the number of bits set in a register. – fuz Nov 27 '22 at 12:24
  • Also, show your effort. – Jester Nov 27 '22 at 12:25
  • Hi so yes im using emu 8086 assembly. I cant use this function . I need to use for loops, shr/shl. – SkyBear Nov 27 '22 at 12:26
  • @SkyBear The 8086 architecture does not have support for for loops. If you have constraints on what the implementation must look like, specify them as clearly as possible. In any way, the [Wikipedia page](https://en.wikipedia.org/wiki/Hamming_weight) has some approaches to computing this function. – fuz Nov 27 '22 at 12:29
  • The canonical link for any bit twiddling algorithm like this is https://graphics.stanford.edu/~seander/bithacks.html The examples are in C but it should be trivial to convert them to assembly if you paid attention in the class, or if you didn't then you can just use godbolt.org – Tom V Nov 27 '22 at 12:59
  • @TomV: C doesn't have a carry flag. If you want an efficient asm loop over bits, it makes sense to use `adc` to sum the bits shifted out by `shr` or `shl`. So compiler output from a C algorithm isn't the best reference for doing it in x86 asm. SO has its own canonical, [Count the number of set bits in a 32-bit integer](https://stackoverflow.com/q/109023), with more emphasis on being able to compile to a `popcnt` instruction on ISAs the support it. Or in x86 asm, [NASM: Count how many bits in a 32 Bit number are set to 1](https://stackoverflow.com/q/2931497) has a tight loop. – Peter Cordes Nov 27 '22 at 14:46
  • [Hamming weight ( number of 1 in a number) mixing C with assembly](https://stackoverflow.com/q/27050583) has a 32-bit MASM answer with mostly the same strategies and nearly the same code. – Peter Cordes Nov 27 '22 at 14:54
  • @PeterCordes: the fastest method on that page works on O(log(N)) time. Anything relying on the carry bit can only be O(N). Since the OP isn't actually trying to solve a real problem but learning then by linking to several algorithms I'm trying to show them that the algorithm is more important than the implementation. Obviously the real answer for most people is just __builtin_popcount(). – Tom V Nov 27 '22 at 15:00
  • @TomV: The top answer on [Count the number of set bits in a 32-bit integer](https://stackoverflow.com/q/109023) suggests the SWAR bithack that only needs O(log2 bitwidth) operations. That's also the first algorithm (after `popcnt eax, edi`) in my NASM answer, but it does cover several algorithms. Of course, learning how to write loops that do something with each bit is a useful exercise; summing them means better algorithms are possible but it's useful for beginners to see the various ways it can be done, even though they're O(bitwidth) or O(popcount) (looping only over set bits). – Peter Cordes Nov 27 '22 at 15:05
  • @PeterCordes: yes it's the same algorithm, but that link has been in my bookmarks since long before stack overflow existed, and it also has loads of other fun/useful stuff. – Tom V Nov 27 '22 at 18:01
  • @TomV: Yeah, fair point about interesting algorithms for other things, and that if you actually care about popcount more than learning how to use x86 shifts and flags, you should look at other popcount algos. One downside to that is that it doesn't use any operations CPUs can do fast but which ISO C fails to expose, e.g. `bsf` / `tzcnt` as building-blocks for other algorithms. But other than that it's good; that's why I added it as the first link in the "references" list in the top answer on [Count the number of set bits in a 32-bit integer](https://stackoverflow.com/q/109023) years ago. – Peter Cordes Nov 27 '22 at 18:22

0 Answers0