SOLVED: Need an idea or algorithm to find numbers between a set of numbers.

Projects Programming
1

Huh?

OK, let me explain... say I have a set of numbers that goes between 0 and 256. Now, take only the values that are represented by a SINGLE BIT, i.e.:

[b]1, 2, 4, 8, 16, 32, 64, 128, 256[/b]

now I want to find the values BETWEEN those numbers, i.e.:

[b]1, 3, 6, 12, 24, 48, 96, 192[/b]

of course, the first number is actually 1.5, but I don't care. The point is that, given ANY number between 1 and 256, I want to return ONLY the ones in-between (they are trigger points for a function).

I don't want to to a hideous "if number < 192 elseif number < 96 elseif blah-blah" kind of thing... I need a simple clean algorithm to do this.

Any ideas will be greatly appreciated!

2

Say the number is 8. The in between number is 8 + 8/2 = 12. If number is 64, 64 + 64/2 = 96.

Is that even close to what you want?

3

I want to find the values BETWEEN those numbers

Do you mean all of the numbers between the single bit numbers or the number halfway between the 2 single bit numbers ?

4

The first step is to clearly and unambiguously define what it is you want to do.

5

groundfungus:
Say the number is 8. The in between number is 8 + 8/2 = 12. If number is 64, 64 + 64/2 = 96.

Is that even close to what you want?

Well, it's part of the idea........

Let's see if I can explain it more carefully... I'm trying to derive a divider number for a clock generator. The divider takes a number from 0 to 8 and in turn divides the input frequency by 1, 2, 4, 8, 16, 32, 64, 128, 256 respectively.

So what I want to do is have a C function that takes in a single INT which can range from 1 to 256 and in turn calculate the proper divider number.

Taking a uint8_t set to 0, then shifting the input value one bit right (or dividing it by 2) and each time incrementing the uint8_t works, but it gives me the divider value AT the bit boundaries (that is, 256, 128, 64, etc...).

It seems to me to be more intuitive if I get the change BETWEEN bit values so that 256...192 gives me 8, 192...96 gives me 7, 96...48 gives me 6, etc...

Make sense?

6

UKHeliBob:
Do you mean all of the numbers between the single bit numbers or the number halfway between the 2 single bit numbers ?

Ah ha! you see it! Yes, ALL numbers between the single bit numbers should return ONE unique result.

For example, ANY number between 256 and 128 should return the same number (in my case, "8").

Then ANYTHING between 128 and 64 should return 7, etc... all the way to the bottom.

(and as I write this, I think I see something... any number between 256 and 129 has bit 8 set, then from 128 down to 65, it's bit 7. I can just make a loop using _BV (x) and check all 9 bits (I think!). Going to try that now... but will still appreciate any ideas and/or better ideas).

7

In a loop, first test the high order bit. If it is set return a value. Otherwise shift left. Is the high order bit set? etc.

Pete

8 
switch (number)
{
  case 128 ... 256:
    out = 8;
    break;
  case 64 ... 127:
    out = 7;
    break;
// and so on
}
}

128 can't be in both cases.

9

Krupski:
I don't want to to a hideous "if number < 192 elseif number < 96

There are only 8 steps

if (x > 127)

else if (x > 64)

etc

The number you are trying to find is (I think) the power to which 2 would need to be raised to get the upper value in the range so it is not a simple process.

...R

10

groundfungus:

switch (number)

{
 case 128 ... 256:
   out = 8;
   break;
 case 64 ... 127:
   out = 7;
   break;
// and so on
}
}





128 can't be in both cases.

OK!!! I didn't know that a range of case values could be specified.

I did try case (div < 256): but the compiler yelled at me.

Although not as "elegant" as I imagine this could be, your code above does the trick. Thank you! And karma++;

11

Just a guess, maybe close:

bitValue = 1
inValue= whatever

for bits = 1 to 64 , bits++

 if  bitValue > inValue  then return bits-1
 bitValue = bitValue*2

next
12

groundfungus:

switch (number)

Well, here's the result and it works like a charm!

    uint8_t n;

    div = div < 1 ? 1 : div > 256 ? 256 : div; // constrain value to legal

    switch (div) {
        case 256 ... 192: {
            n = 8;
            break;
        }
        case 191 ... 96: {
            n = 7;
            break;
        }
        case 95 ... 48: {
            n = 6;
            break;
        }
        case 47 ... 24: {
            n = 5;
            break;
        }
        case 23 ... 12: {
            n = 4;
            break;
        }
        case 11 ... 6: {
            n = 3;
            break;
        }
        case 5 ... 3: {
            n = 2;
            break;
        }
        case 2: {
            n = 1;
            break;
        }
        case 1: {
            n = 0;
            break;
        }
        default: { // this should never happen but good it's programming practice
            n = 0;
            break;
        }

Thanks again!!!

13

I'm not quite sure what your code is supposed to do, but making loop decisions on bit values results in the divider switching AT bit values, not between them as I want.

Also, the switch/case idea that groundfungus gave me works great.

Thank you for your input!

14

"but making loop decisions on bit values results in the divider switching AT bit values, not between them as I want."

Are there only one result between bit values, or do you expect several results between bit values?

I thought you only wanted one result between bit values. 2 bits, 3 bits, etc. not 2.4 bits, 3.6 bits. I am probably confused.

15

Could not resist
Simple if then ladder, no constrain needed as it is build in.
Max 8 compares, on average ~2.45 (if numbers are divided equally)

    uint8_t n = 0;
    if (div >= 192) n = 8;
    else if (div >= 96) n = 7;
    else if (div >= 48) n = 6;
    else if (div >= 24) n = 5;
    else if (div >= 12) n = 4;
    else if (div >= 6) n = 3;
    else if (div >= 3) n = 2;
    else if (div >= 2) n = 1;

If you really want to squeeze performance you might consider a binary search tree...

16

How about this function?

void setup() {
  Serial.begin(9600);
  for (int i = 255; i >= 0; i--)
  {
    Serial.print(i);
    Serial.print(" ");
    Serial.println(twinBits(i));
  }
}

void loop() {
}

// finds the highest bit, but with the next lower bit set.
// Unknown purpose.

byte twinBits (byte v)
{
    byte bitpos = 8;
    while ((v & 0x80) == 0) {
      v = v<<1;
      bitpos--;
    }
    if ( ((v<<1)& 0x80) == 0) bitpos--;
    return bitpos;
}
17

robtillaart:
Could not resist
Simple if then ladder, no constrain needed as it is build in.
Max 8 compares, on average ~2.45 (if numbers are divided equally)

    uint8_t n = 0;

if (div >= 192) n = 8;
   else if (div >= 96) n = 7;
   else if (div >= 48) n = 6;
   else if (div >= 24) n = 5;
   else if (div >= 12) n = 4;
   else if (div >= 6) n = 3;
   else if (div >= 3) n = 2;
   else if (div >= 2) n = 1;




If you really want to squeeze performance you might consider a binary search tree...

Performance is not an issue at all. This function is only called once or twice in the entire lifetime of the program using it.

By the way, as I thought about it, I realized that what I wanted was a logarithmic curve, so I just generated a small data file (like this):

[tt][b]384, 8
192, 7
96, 6
...
6, 2
3, 1
1, 0[/b]

[/tt]then curve fit it, then used the equation and coefficients to generate all the points. Lastly, I took the first and last of each value that generated "8" and put them into one case statement, all the ones that generated "7", etc... so now I get a perfectly centered result based on the input value.

Here's the final, finished code:

//
// clockDivide.cpp
//

#include "wiring_private.h" // for uint8_t and CLKPCE

uint8_t clockDivide (int div)
{
    uint8_t n;
    uint8_t oldSREG;

    div = div < 1 ? 1 : div > 256 ? 256 : div; // constrain value to legal

    switch (div) {
        case 192 ... 256: {
            n = 8;
            break;
        }
        case 100 ... 191: {
            n = 7;
            break;
        }
        case 52 ... 99: {
            n = 6;
            break;
        }
        case 27 ... 51: {
            n = 5;
            break;
        }
        case 14 ... 26: {
            n = 4;
            break;
        }
        case 8 ... 13: {
            n = 3;
            break;
        }
        case 4 ... 7: {
            n = 2;
            break;
        }
        case 2 ... 3: {
            n = 1;
            break;
        }
        case 1: {
            n = 0;
            break;
        }
        default: {
            n = 0;
            break;
        }
    }

    oldSREG = SREG; // save status register state
    __asm__ __volatile__ (" cli\n"); // interrupts off

    CLKPR = _BV (CLKPCE); // enable prescaler change
    CLKPR = n; // set clock divider

    SREG = oldSREG; // restore SREG state

    return n; // return divider number for other possible uses
}

See what it does? It allows changing the AVR clock divider on the fly within a sketch (I'm sure someone will ask me "why would you want to do that?") :slight_smile:

18

aarg:
How about this function?

Now THAT'S what I had in mind... something clean and elegant. This is even nicer than the switch/case method.

I had to modify your code slightly (change the incoming data for "twinBits" from a uint8_t to an int to be able to handle 256 and also compare to bit 8 (0x0100) instead of bit 7 (0x80) again to be able to handle 256).

Here's your code as I tested it here and it works like a charm!

// finds the highest bit, but with the next lower bit set.
// Unknown purpose.

uint8_t twinBits (int v)
{
    uint8_t bitpos = 9;
    while ((v & 0x100) == 0) {
        v = v << 1;
        bitpos--;
    }
    if (((v << 1) & 0x100) == 0) {
        bitpos--;
    }
    return bitpos;
}

int main (void)
{
    init();

    Serial.begin (115200);

    int i;

    for (i = 1; i <= 256; i++) {
        Serial.print (i);
        Serial.print (" ");
        Serial.println (twinBits (i));
    }

    while (1);
}

Thank you! A karma++ for you also. :slight_smile:

19

aarg:
How about this function?

Here's the final code using your idea and it's great. Nice, compact and it works like a charm.

uint8_t clockDivide (uint16_t div)
{
    uint8_t n = 9;
    uint8_t oldSREG;

    div = div < 1 ? 1 : div > 256 ? 256 : div; // constrain value to legal

    while (! (div & 0x0100)) {
        div <<= 1;
        n--;
    }

    if (! ((div << 1) & 0x0100)) {
        n--;
    }

    oldSREG = SREG; // save status register state
    __asm__ __volatile__ (" cli\n"); // interrupts off
    CLKPR = _BV (CLKPCE); // enable prescaler change
    CLKPR = n; // set clock divider
    SREG = oldSREG; // restore SREG state
    return n; // return divider number for other possible uses
}

That's the way - uh-huh uh-huh - I like it! :slight_smile:

20

@Krupski: aarg's code just implements what I said in msg #6. I had assumed you could do the coding yourself.

Pete