0

I know how make bit operation. I'm wondering if you need more than 2 states is there a way to do it using bit instead of array and % operators. Because those are really slow.

So in case the array save state for 4 semaphores {0,1,2}

0000 + 0001 = 0001
0001 + 0001 = 0002
0002 + 0001 = 0000
0002 + 2002 = 2001

Now i can do

int[] a = new int[4]{0,0,0,2};
int[] b = new int[4]{0,0,0,2};

for (int i=0; i < a.length; i++) {
   a[i] = (a[i] + b[i]) % 3;
}

What is the best way to do this?

  • 2
    Unless you can find a ternary logic system... probably. – user40980 Jun 13 '15 at 1:29
  • You could try doing it in chunks of 2 bits and see if it gives any performance improvement. – Rufflewind Jun 13 '15 at 3:05
  • Chunks of 2 bits won't work since it doesn't leave enough room for intermediate values >3. Chunks of 3 bits will, you'll just have to implement the reduction using bitwise operations. – CodesInChaos Sep 11 '15 at 10:39
1

You can stack bits together to keep track of any number of state values as you need.

If you need to keep track of 4 state values then use 2 bits.

Each bit gives you 2 values. 2 bits gives you 2x2.

I am not sure why you have lumped together array operators and % as if they are the same category of operation. % is a a modulo operator. I wouldn't consider that operator to be slow.

Of course stacking bits can result in expressions that can seem complex, but what is the priority? Is it readability or performance? Do you want to be efficient in the use of space to store your data?

To use data organised as 2 bit elements, the 4-int array you have got will be replaced by just one int.

On most systems int will be at least 2 bytes--so that's more than enough to hold 4 2-bit values (or "semaphores" as you say).

You would do well to confirm what the size of int is on your system.

And you can try this code:

int a = 0b10000000; // 4x2 bit value equivalent to: new int[4]{0,0,0,2};
int b = 0b00000011; // first item value is 3
size_data = 4;

for (int i=0; i < size_data; i++) {
   // expression: i*2 gives index for shr
   //             a >> i*2 & 0x03 gives the value of a
   //             b >> i*2 & 0x03 gives the value of b
   printf("i=%d   i*2=%d   a=%d b=%d\n", i*2, a >> i*2 & 0x03, b >> i*2 & 0x03);
}
  • 1
    I convert to c# dotnetfiddle.net/VFJPBw please check the result is correct. What does the 0x03 part? And I dont see the a + b part. – Juan Carlos Oropeza Jun 13 '15 at 5:00
  • I actually don't understand the a+b part in your question. Particularly, why is 0002 + 2002 = 2001? Anyway, if all you want to do is just a+b... if you understand the logic of the code so far, then should be able to easily add a+b. – user55570 Jun 13 '15 at 7:34

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.