Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.misc > #17726

Re: Thoughts in combinatorial logic

Show all headers | View raw

Sylvia Else <sylvia@email.invalid> wrote:
> As part of a personal project I'm working on, I needed a combinatorial 
> logic way of obtaining the lowest set bit from a collection of bits. 
> That is, taking n inputs in some order, and by using only and/or/not 
> gates, produce n outputs of which only one is set, being that which 
> corresponds to the lowest order set input bit
> 
> It's not especially difficult.
> 
> But suppose the requirement is not the lowest set bit, just any of the 
> set bits.
> 
> Clearly, the solution to the first requirement is also a solution to the 
> second requirement, but is the second requirement amenable to a simpler 
> (as in, using fewer gates) solution.
> 
> My intuition is that it's not, but I haven't been able to prove it.

A mathematical proof is beyond me, but after mulling over it for a
while I can't think of a way in which the latter problem would have
a simpler solution to the former.

For the lowest set bit, you need for the set bits following the
first one to be cleared. For "any set bit", you need all the set bits
but one to be cleared. Clearing the bits in both "directions" is
harder than only in one direction, as far as I can see.

Another approach would be something like an address decoder
arrangement, and that would be more complicated than clearing the
following bits. In fact I think the second problem may be directly
implying something that would equate to an address decoder.

-- 
__          __
#_ < |\| |< _#

Back to comp.misc | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Thoughts in combinatorial logic Sylvia Else <sylvia@email.invalid> - 2019-04-01 16:11 +1100
  Re: Thoughts in combinatorial logic Marko Rauhamaa <marko@pacujo.net> - 2019-04-01 16:28 +0300
  Re: Thoughts in combinatorial logic not@telling.you.invalid (Computer Nerd Kev) - 2019-04-02 22:08 +0000
    Re: Thoughts in combinatorial logic not@telling.you.invalid (Computer Nerd Kev) - 2019-04-03 07:47 +0000
  Re: Thoughts in combinatorial logic Bruce Horrocks <07.013@scorecrow.com> - 2019-04-02 23:11 +0100
    Re: Thoughts in combinatorial logic Sylvia Else <sylvia@email.invalid> - 2019-04-03 09:34 +1100
  Re: Thoughts in combinatorial logic Bruce Horrocks <07.013@scorecrow.com> - 2019-04-05 10:48 +0100
    Re: Thoughts in combinatorial logic Sylvia Else <sylvia@email.invalid> - 2019-04-11 20:33 +1000

csiph-web