Generate number sequences using bit operations

[crisc]

Hi,

I often find myself needing to produce simple number sequences that often do not exceed 4 numbers, for example
0 1 1 0 or 1 0 -1 0 or 1 1 -1 -1 or 1 -1 0 0

I'm wondering if there is some way to generate a formula of bit operations quickly by providing the desired sequence? (It often comes down to a little bit shifting, ANDs, and XORs.)

Just wondering if anyone else might have encountered this (and maybe has a solution to it). I always sit down then and cook up some formula thinking someone else must have done that before.

Thanks,

crisc

[quzah]

Generate the sequence:

unsigned char sequence = rand() & 0xFF;

Show:

void showsequence( unsigned char s )
{
    while( s )
    {
        printf( "%c%c%c", s & 0x40 && s & 0x10 ?'-':' ', '0'+!!(s & 0x10), s << 2 == 0 ?' ':'\n' );
        s <<= 2;
    }
}

That looks about right.


Quzah.

[crisc]

Oops, I left out an important detail: I need to be deterministic in creating such sequences.

For example, an algorithm should 'walk' along the edges of a square so that it outputs all the corners of the square. If you want to start in the top left corner and walk clockwise and the length of an edge is r, you can use a

sequence for x: 0 1 1 0, let's assume this is created by a sequence function int sx(int i)
sequence for y: 0 0 1 1, similarly by int sy(int i);

to easily calculate the coordinates using a loop. That way, you just do this

for(int i=0; i!=4; i++) {
    int px = r * sx(i);
    int py = r * sy(i);
    printf("coordinate: %d,%d\n", px, py);
}

So the sequence cannot be random. My intention was to ask how I can generate a function like sx() or sy() in this case if I only have the output of that function. Sorry for leaving this unclear.

crisc

[quzah]

Of course the sequence can be random. You only have 256 possible combinations (actually less, since you cannot have a negative zero*). I can make a function that will take any of those and draw a square from it. Really, you would end up with even less possible options:

-/-,-/0,-/+
0/-,0/0,0/+
+/-,+/0,+/+

--/--, means you have a square of 1 element in size, with all four points in the same spot. The same would fall for the eight other four "same" coordinate options. You then have four boxes possible that span 2 different coordinates (-/- to 0/0; -/0 to 0/+, -/0 to 0/+) and finally one more that spans the whole thing (-/- to +/+ [edit2: technically there are two: +-/-+, if we draw from the other pair of corners, which I suppose doubles up the previous possible sets from four to eight as well, since --00 can also be done from -00-. I guess it really depends on if I define the box as what four points it encompasses, or from which of its points I start drawing, since with all but same-point boxes, you can start drawing from any one of its four points and end up having drawn all the same four corners.] ).

The function doesn't care what the sequence is, it just plots all the points or draws a box, or whatever it is. For example, I could make a function that took a byte for input, and using the method I showed you in the first post to look at all the bits, fill out a 9/9 array with the path it walked, drawing all of those boxes for you:

[*][*][-]
[*][*][-]
[-][-][-]

Looking at my output, four different coordinate pairs could have drawn that same box. I could have provided you: --00, -00-, 00-- or 0--0.


*You illustrated three different possible values, which requires 2 bytes to represent, wasting 1/4th of your possible combinations, since negative-zero and zero are effectively the same thing in math, and which would have given you an additional unused value, so you are forced to work around it. Note also that in the example above "-00-" is not representing "negative-zero", rather it is as shown in image 1, pairs of coordinates ranging from negative/negative to positive/positive.

Anyway, I wasn't providing some manner of useful sequence generation, since you said nothing about that, rather I was illustrating how to squish your small number range into a few bits, since that was what you were requesting.


Quzah.

[iMalc]

For a sequence of just two numbers (A and B) it's easy. The following code will toggle between them:

n = (A+B) - n;

For three or more, a simple option is to use a lookup table. That table can either be explicitly written out the long way, which is highly readable:

// 1, 0, -1, 0
const int table[] = {1, 0, -1, 0};
n = table[index];
index = (index+1) % (sizeof(table)/sizeof(table[0]));

or can be just packed into an int:

// 1, 0, -1, 0
n = (char)(0x00FF0001 >> (((index++)&3)*8));

Of course for a lot of common sequences, there are arithmetic ways that you are thinking of, such as:

// 0, 1, 1, 0
n = (index ^ (index>>1)) & 1;
++index;

Which yes I just wrote on the spot.
Generating code for such sequences can take a bit of clever thinking and/or some experience in doing so. But whenever that is too hard, just use the lookup table way of doing it.

[quzah]

The problem I have with this thread is that he doesn't sound like he knows what he really wants. What's he asking here?

How do I generate a hash (a "sequence" from some unexplained data points)?
How do I draw a box with a set of coordinates packed into a single variable?
Or something completely different?

First he says he wants to generate some numbers from -1, 0 or 1. Then he says he wants to draw a box based on some numbers from a "deterministic sequence". Which is completely different than what he was asking before. First he wanted to make numbers, now he want's to make to take the numbers and do something with it.

To me, he doesn't sound like he knows what he is wanting.


Quzah.

[iMalc]

To me, it's clear that he wants to know how people come up with code such as per my post above, which will generate a given sequence (the last code snippet in particular). The answer is that it's mostly just experience and skill.
One can also write a genetic algorithm to attempt to generate the code for generating any given sequence. As it happens, I've also gone a fair way down that path before, but that's kind of like forging your own steel to make your own knife, to cut a piece of cake.

[quzah]

What sequence though? Based on what? With what input parameters? That's my whole point. Otherwise all he has to do is write something that spits out every combination of -1/0/1 for however many digits he wants. Without any specifics on what determines what the sequence is based off of, he may as well be generating random numbers.

We can't build him a sequence with no start or finish. That's like me telling you to count, and then telling you that you counted wrong.

"You didn't tell me you wanted to count by fives!"
"I didn't tell you I wanted you to count backwards either, hah!"

Without specifying what the sequence is based on, it may as well just be completely random numbers, and he can randomly strip bits off it as he chooses. It has no meaning without context.


Quzah.

[iMalc]

If I understand it right, this is a question about the process of learning how to write the code, and he doesn't necessarily have a specific sequence in mind besides the examples given. For his second post example the result would be:

int sx(int i) { return (i ^ (i >> 1)) & 1; }
int sy(int i) { return (i >> 1) & 1; }

but this doesn't explain how I came up with it.

Reading and coming to understand some of the stuff on this page will help you figure out how to figure out such things. Then it's just practice practice practice.

[crisc]

Thanks iMalc. Yes, I'm not too skilled of a programmer yet and it always takes me 1-2 min to come up with a formula to generate a desired sequence. The lookup approach seems like the easiest way to go for me.

quzah:
Sorry for causing confusion. All I had in mind was to replace a concatenation of if statements with arithmetics inside a for loop (input = integer counting from 0 up).

For getting the coordinates of the square, one could also do

if (i == 0) {
    // top left
    ...
} else if (i == 1) {
    // top right
    ...
} else if ...

Having a formula produce a sequence of 0s and 1s so as to just multiply with width and height is certainly a lot easier (although might not be easier to read in code).

Thanks both!

crisc