Member Avatar for wnr78ta

Hi, I am working on a program that uses an array of integers(1 and 0) to represent a gray code. For this to work I first have to take an integer and convert it to the binary, then convert the binary to gray code. The for loops i use to do this are shown below.

//Calculate Next State
     my_timer_UI32++;
     for(i = 0; i < SIZE; i ++){   //Decimal to binary conversion
          graycode_I16[SIZE-1-i] = (int)((my_timer_UI32 >> i) & 1);
    }

    for(i = SIZE-1; i > 0; i --){ //binary to gray code
        graycode_I16[i] = graycode_I16[i] ^ graycode_I16[i - 1];
    }

My problem with this is that this graycode holds time in milliseconds so inorder to increment this I have to increment the decimal time in ms, then convert to binary, then convert to graycode again and this is taking far more time than I would like. So my question is, would it be possible to increment graycode_I16 to so that it would increment the ms by 1? Hopefully this is detailed enough, if you need more details let me know.
Thanks!

  • 2 Contributors
  • 1 Reply
  • 812 Views
  • 19 Hours Discussion Span
  • Latest Post Latest Post by Banfa

Dani AI

Generated

Short answer: yes — you do not need to rebuild the whole Gray array every millisecond. A reflected Gray code changes exactly one bit when the binary counter increments; which bit to toggle depends only on the run of trailing 1s in the binary counter before the increment. That gives an O(1) update: compute the position and flip that single bit.

Why it works (one sentence): if the binary value before increment has r trailing ones, then the Gray vector for the next value differs from the current one by a single bit at index r (0 = LSB); if the counter is all ones (overflow within SIZE bits) toggle the MSB.

Example implementation (fits the array layout in your post where LSB is stored at index SIZE-1):

/* my_timer_UI32 holds the binary counter (unsigned).
   graycode_I16[...] stores bits with LSB at index SIZE-1. */

unsigned old = my_timer_UI32;
unsigned mask;
if (SIZE >= (int)(8 * sizeof(unsigned))) mask = ~0u;
else mask = (1u << SIZE) - 1u;

unsigned v = (~old) & mask;   // trailing ones of old -> trailing zeros after invert
unsigned r;
if (v == 0) r = SIZE - 1;     // overflow: toggle MSB
else {
#if defined(__GNUC__) || defined(__clang__)
    r = __builtin_ctz(v);     // fast: count trailing zeros
#else
    r = 0; while (((v >> r) & 1u) == 0) ++r;
#endif
}

int idx = SIZE - 1 - (int)r;   // map LSB-based position into your array index
graycode_I16[idx] ^= 1;        // toggle the single bit
my_timer_UI32 = (old + 1u) & mask;

Notes and pitfalls:

  • Use unsigned arithmetic and mask to SIZE bits to avoid UB.
  • __builtin_ctz is undefined for zero, so v == 0 is checked first.
  • This is equivalent in effect to the single-bit-flip approach suggested, but implemented with a cheap bit test instead of scanning/convert loops.
  • If your array stores LSB at index 0 instead, drop the SIZE-1- mapping.
Member Avatar for Banfa

You can increment using something like this assuming a grey code number with n bits numbered from LSB 0 to MSB n-1

Get the count of the number of bits set to 1

if count is even
    invert bit 0
else
   set j = the number of the least significant bit set to 1
   if (j == n-1)
       invert bit j
   else
       invert bit j+1
   endif
endif

I kind of worked this out emperically rather than finding a proof for it so you may wish to verify it over a wide range of numbers.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.