0
\$\begingroup\$

I want to check (in hardware) whether a bit is on (1) in a 64 bit number - the bit I want to check can be any bit but I'm only interested in checking that one bit.

I get the number -ie offset - of the bit as a 6 bit number eg if that number is 0 I need to check bit 0, if the number is 17 I need to check bit 17 etc.

Is there anything faster (even if more costly in power and area) than this idea:

  1. Input (bit I want to check) is X - so use a barrel shifter to left shift 1 by X and store result in Y
  2. Then Z<-(Y AND Bitmap)
  3. OR together all bits in Z - if output is 1 then bit is on, otherwise bit is off.

I suspect that 1 is the costly operation, so any ideas about a faster way of doing that would be particularly welcome.

\$\endgroup\$
  • \$\begingroup\$ 1/ Read the value, 2/ AND with a 64 bit mask. 3/ Check if the result is zero (or not). If your CPU is not 64 bits wide read only the byte/word/halfword with the bit you want to test and do the same at a different width. \$\endgroup\$ – Oldfart Nov 25 '19 at 13:49
  • \$\begingroup\$ How will your hardware be provided with that 64bit number? 64 distinct lines? If so, one possibility might be: 64 and gates, one input your data, the other input is your bit-selecting-line. or all those outputs together (if you want to use TTL components, there should be 8-input or-gates available. 9 of them in two layers would do the trick.) \$\endgroup\$ – DThought Nov 25 '19 at 15:12
  • \$\begingroup\$ @DThought - I get it as a 6 bit number - I need to make the question clearer I think - because the number tells me which bit I need to check. \$\endgroup\$ – adrianmcmenamin Nov 25 '19 at 15:38
  • \$\begingroup\$ @adrianmcmenamin the question was how you get the 64 bit value to check, you already clarified that the bit that it is desired to test is provided as an ordinal bit number. You also need to specify how often the value changes, how you know it has finished changing to a new value and is now valid, and what delay in producing an output is acceptable. And similarly provide timing for the specification of the test bit. These will help determine if your design can be synchronous, if it can be pipelined, and if the best actual solution is even hardware vs software at all. \$\endgroup\$ – Chris Stratton Nov 25 '19 at 16:53
4
\$\begingroup\$

I'm assuming you want to do this in hardware, rather than software, because of the tags you selected.

I suspect that the fastest implementation would be to use a 64-to-1 multiplexer with X as the select input. The output of the multiplexer is the bit value you want to check. No additional logic is needed...if the mux output is 1 then the bit you want to check is 1, and vice versa.

The actual implementation of the mux itself may depend on how you intend to build the thing. In CMOS VLSI it might be best to use six levels of 2:1 multiplexers. In an FPGA just write the Verilog and let the tools do the heavy lifting.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Yes, in hardware - I thought it was obvious coming to an electric/electronic engineering site - but I'll make it explicit in the question, thanks. \$\endgroup\$ – adrianmcmenamin Nov 25 '19 at 14:12
  • \$\begingroup\$ @adrianmcmenamin - no, that is not obvious at all, because with rare exceptions which are not likely to apply to your situation, the best way to solve such a problem is in embedded software. Fast 64-bit parallel busses actually necessitating a pure logic solution are fairly rare, and just about non-existent in contexts where it would be practical for someone of limited design experience to directly interact with them. \$\endgroup\$ – Chris Stratton Nov 25 '19 at 16:38
  • \$\begingroup\$ @elliotAlderson - just to ensure I have understood you correctly - I'd need 64 of these, right? Eg the first would give me 1 on an input of 0x00, the second 1 on 0x00...2, the tenth on 0x00...A and so on? \$\endgroup\$ – adrianmcmenamin Nov 25 '19 at 20:30
  • 1
    \$\begingroup\$ No, you just need one 64:1 multiplexer. The inputs to the mux are your 64-bit word and the 6-bit value that tells you which bit you care about. The output of the mux is the single bit you care about. \$\endgroup\$ – Elliot Alderson Nov 25 '19 at 22:35
1
\$\begingroup\$

Assuming you have a 64-bit number, and that you must use software (no fancy peripheral to output the value), then you must do the following:

  1. Initial read of the input value (peripheral, memory location, or otherwise)
  2. Bitmask the input: x & 0b0001000000000000000000000000000000000000000000000000
  3. Check if the masked value is greater than zero, or equal to zero if you want to invert this logic

This is a rather common operation, so perhaps some CPU's have special instructions for this operation, but I'm not well-read on cpu instruction sets.

Notes:

0b010 is shorthand for a value specified using binary syntax.

I didn't count out 64 zero's in my bitmask.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks, but it wasn't a software question - that's why I asked it here. \$\endgroup\$ – adrianmcmenamin Nov 25 '19 at 14:14
  • 1
    \$\begingroup\$ At least this this illustrates why C doesn't have binary integer constants. That would be because they are completely unreadable. \$\endgroup\$ – Lundin Nov 25 '19 at 14:33
  • \$\begingroup\$ Yeah it was mostly for illustrative purposes. I do find myself using them for smaller bitmasks though. GCC C compiler extensions do have binary integer constants. According to stackoverflow.com/questions/16334024/… C++14 also added binary constants supports. \$\endgroup\$ – gregb212 Nov 25 '19 at 16:04
  • \$\begingroup\$ @adrianmcmenamin , apologies. Embedded questions do usually pop up on here from time to time. But my answer could still apply to a discrete logic solution. \$\endgroup\$ – gregb212 Nov 25 '19 at 16:06
  • \$\begingroup\$ @gregb212 no problem - I don't quite follow your answer though - why would I want to bitmask (to 1?) with 0x1000000000000000? \$\endgroup\$ – adrianmcmenamin Nov 25 '19 at 20:20
-1
\$\begingroup\$

With thanks to @ElliotAlderson and to assist anyone else looking for an answer - an example Mux that has a two bit selectenter image description here and does the sort of thing I want - albeit with just a 4 bit input and output.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.