Converting a bit-value to an integer

Projects Programming
1

Hi,

Is there a fast bitwise operation which would do the opposite of a bitshift, i.e. result in the integer required to shift into another integer? I'm trying to convert, as fast as possible, an input from a shift register into a value in a array. The array has indexes from 0 to 7 (with a byte in each index), while the input goes from 128, 64, 32 to 1.

128 -> 0
64 -> 1
32 -> 2

What's the fastest way to do this?

Alternatively, if I build the array with indexes 1, 2, 4, 8 instead of 0, 1, 2, 3, would it be very inefficient or memory hungry?

Thanks.

2

Something like that :

bool register[8];

int result=0;
int shift=7;

for(int i=0; i<8; i++)
  result += register[i]<<shift--;

code not tested...

3

Thank you, I was hoping of not using a for loop but it looks like there's no other way...

4

I can immediately think of two possible solutions.

  1. Examine bit 0, shift right if not set, increment counter, repeat. Counter is bit number.
  2. A nice big fat switch.

I'm not sure which would be more efficient.

(untested) code examples:

method one:

byte incoming=64;
byte counter=0;

for(; (incoming&0x01==0) && (counter<8); counter++)
  incoming=incoming>>1;

method two:

byte incoming=64;
byte index;

switch(incoming)
{
  case 1:    index=0; break;
  case 2:    index=1; break;
  case 4:    index=2; break;
  case 8:    index=3; break;
  case 16:   index=4; break;
  case 32:   index=5; break;
  case 64:   index=6; break;
  case 128:  index=7; break;
}
5

Thanks a lot, it confirms that no "direct" operation exists and that a loop/switch will always be needed.

I found something on a C forum where someone proposed to use a simple "lookup table" for this sort of thing. What is that, and can that be used in this context?

6

A lookup table would be much like the switch, or using an array with 256 elements.

It would be the fastest, but would be inefficient on storage. You would really need to ensure that the array was held in PROGMEM, and that adds its own overheads. Yes, it would fit in RAM, but 256 bytes out of 2K is quite a chunk.

7

Ischia:
Hi,

Is there a fast bitwise operation which would do the opposite of a bitshift, i.e. result in the integer required to shift into another integer? I'm trying to convert, as fast as possible, an input from a shift register into a value in a array. The array has indexes from 0 to 7 (with a byte in each index), while the input goes from 128, 64, 32 to 1.

128 -> 0
64 -> 1
32 -> 2

What's the fastest way to do this?

Alternatively, if I build the array with indexes 1, 2, 4, 8 instead of 0, 1, 2, 3, would it be very inefficient or memory hungry?

Thanks.

The shift register, you get values from it whole through SPI or I2C or other serial? Normally that is the connection but no, it doesn't have to be.

It looks like you want to put each bit into a separate byte. But... why? The data only becomes harder to read and takes 8x the memory space! To what end is that that cannot be served more simply by reading bits in the same byte?

What are you trying to engineer around? Not the solution, the problem the solution is for?

8

What are you trying to engineer around?

I have an array which stores bytes, each one representing a sequence (think of a musical sequence).

For example, "01001000" is a meaningful sequence — both visually and musically, read from left to right.

An array holds 8 of those. Imagine each element of the array representing a different light, led, key, person holding a mallet, whatever.

So the array looks like that:

byte sequence[8] =
  {
    B00000010,
    B10011000,
    B00000000,
    B00000000,
    B00000010,
    B00100000,
    B00000000,
    B00000000
  }

Now, when reading the state of eight buttons through the shift register (using software "digitalRead", I don't know how to communicate with SPI yet), I come up with a value which can be 128, 64, 32, depending on which button was pressed. I'd like that value to correspond to an element in the array (i.e. 128 should choose the first element, 64 the second etc).

I read the button values like that because it's then very easy to set flags and check values (the buttons do other stuff except selecting elements from the array).

I hope I'm being clear with this, I'm programming and posting at the same time :slight_smile:

9

Alternatively, if I build the array with indexes 1, 2, 4, 8 instead of 0, 1, 2, 3, would it be very inefficient or memory hungry?

You cannot chose the indexes like that, if the max number is 8 then that's not many entries there must be in the array. You may choose not to use them all but that's another story (actually it's a lookup table).

What's the fastest way to do this?

A lookup table. Look it up :slight_smile:

In your example you need an array of 128 bytes where

byte #128 == 0
byte #64 == 1
byte #32 == 2

and all the other bytes are not used. This is a sparse array and in this case at least it's VERY inefficient in space but the fastest way to get the values you need.

Do you really need that much speed? What's wrong with using a loop?

Rob

10

If you are manually reading the shift registers with digitalRead, why not just count the number of bits until you hit a 1 within your reading routine? Scrap the 1,2,4,8,16, etc, and just use 1,2,3,4,5, etc

11

why not just count the number of bits

My mistake, I used digitalRead when checking stuff manually in an earlier version. I'm now using shiftIn entirely. So, you're suggesting I either rewrite shiftIn slightly and just hold two variables at all times, the number of bits counted + the bitwise value of the button?

I didn't think it would be this complicated, I don't have a lot of experience and I thought conversions like that were something common :slight_smile:

12

I am sure the most complicated thing is trying to use spoken language (English) to convey logical ideas, errr, incompletely.

more soon

13

Questions and answers will narrow understanding towards truth.

Now you use shiftIn, you get all the buttons pressed at once as bits in a byte or int?

14 
sw = shiftIn (...);

but_pressed = 0;

for (int i = 0; (i < 8) && (but_pressed == 0); i++) {
    if ((sw & 1) == 1)
       but_pressed = i;
}

if (but_pressed) {
    seq = sequence [but_pressed];
}

EDIT: () replaced with []

Rob

15

@Graynomad: similar idea to majenko's "for" loop above, no?

@GoForSmoke: I read them in a byte. For now multiple presses are not handled, so I just cater for 128, 64 etc.

16

Similar but I think he is checking for a bit number when we were less clear about the requirements.

Rob

17

gcc has an extension that allows ranges in switch statements

inline byte ConvertValue( byte input )
  {
    switch( input ){
     
       case 128 ... 65:  return 0; break;
       case 64 ... 33:   return 1; break;
       case 32 ... 17:   return 2; break;
       case 16 ... 9:    return 3; break;
       case 8 ... 5:     return 4; break;
       case 4 ... 3:     return 5; break;
       case 2:           return 6; break;
       case 1:           return 7; break;
       default:          return -1; break;
    }
  }

maybe something like this may suffice, replace the return values with something meaningful, or use them as an index.

18

@pYro_65: in Reply#3 @majenko's second method works just fine (I've tested it in the last hour, no problems). It's just that @GoForSmoke was implying another method might exist.

Like I said, I understand now that it boils down to a loop or a switch, whereas I was originally hoping for a single bitwise-like operation.

Thanks very much to everyone!

19

inline byte Conve...
..
... return -1;

Um... Byte? -1? :stuck_out_tongue:

20

Ischia:
@pYro_65: in Reply#3 @majenko's second method works just fine (I've tested it in the last hour, no problems). It's just that @GoForSmoke was implying another method might exist.

Only if you were taking bits shifted in that belong together and putting them into array bytes. In that case what you would do with the bits could be as well done in 1 byte as in an array of 8.

Truth is, I am not sure you need the array at all. If a button is pressed later, does it go to the same array? If so then think of a byte as an array of 8 bits. You can read any of them using the bitRead() function. Even having your byte array, how will you read from that any easier? You won't.

Really if 1 button at a time you should reject all inputs that have more than 1 bit set as errors. The same loop you use to check for data can check for errors.

Like I said, I understand now that it boils down to a loop or a switch, whereas I was originally hoping for a single bitwise-like operation.

Bits don't address bytes.

I think that the problem is in your solution. When you step back from the byte array it may become more clear.