8-digit BCD check

Question

I've a 8-digit BCD number and need to check it out to see if it is a valid BCD number. How can I programmatically (C/C++) make this?

Ex: 0x12345678 is valid, but 0x00f00abc isn't.

Thanks in advance!

OP is probably an EE, (where it is assumed you know wha BCD is). — Eric S., Mar 20 '15 at 20:55
Do you mean you want to check if your binary represents a valid BCD number? Meaning 1010 is not valid, but 0010 is? — Eric S., Mar 20 '15 at 21:00
@JonathanPotter BCD = Binary Coded Decimal. Back when I first started in computers it was a well known term; now probably not so much. — Mark Ransom, Mar 20 '15 at 21:20
@JonathanPotter If you click on the "BCD" tag, you can find out more about it. — Sneftel, Mar 20 '15 at 21:29

Mark Ransom · Answer 1 · 2015-03-21T02:44:07.630

You need to check each 4-bit quantity to make sure it's less than 10. For efficiency you want to work on as many bits as you can at a single time.

Here I break the digits apart to leave a zero between each one, then add 6 to each and check for overflow.

uint32_t highs = (value & 0xf0f0f0f0) >> 4;
uint32_t lows = value & 0x0f0f0f0f;
bool invalid = (((highs + 0x06060606) | (lows + 0x06060606)) & 0xf0f0f0f0) != 0;

Edit: actually we can do slightly better. It doesn't take 4 bits to detect overflow, only 1. If we divide all the digits by 2, it frees a bit and we can check all the digits at once.

uint32_t halfdigits = (value >> 1) & 0x77777777;
bool invalid = ((halfdigits + 0x33333333) & 0x88888888) != 0;

I `+1`'d as this is neater than mine (if slightly less obvious and extensible). — abligh, Mar 20 '15 at 21:34

abligh · Answer 2 · 2015-03-20T21:40:40.713

3

The obvious way to do this is:

/* returns 1 if x is valid BCD */
int
isvalidbcd (uint32_t x)
{
    for (; x; x = x>>4)
    {
        if ((x & 0xf) >= 0xa)
            return 0;
    }
    return 1;
}

This link tells you all about BCD, and recommends something like this asa more optimised solution (reworking to check all the digits, and hence using a 64 bit data type, and untested):

/* returns 1 if x is valid BCD */
int
isvalidbcd (uint32_t x)
{
   return !!(((uint64_t)x + 0x66666666ULL) ^ (uint64_t)x) & 0x111111110ULL;
}

edited Mar 20 '15 at 21:40

answered Mar 20 '15 at 21:30

abligh

24,573
4
47
84

Why obfuscate the natural operations? You're not shifting by 4, you're dividing by 16 (the base of hex numbers). You're not anding with 0xf, you're modding by 16 (the base of hex numbers). If you don't obfuscate your operations, it's easy to see that this algorithm is generic for looping through the digits of numbers of *any* base. Just substitute 10 instead of 16 for decimal numbers. 2 instead of 16 for binary. Etc. Self documenting code. – indiv Mar 20 '15 at 21:40
1

Personally I think of it as looking at the bits in groups of 4. Node that `& 0xf` is equivalent to taking the modulus `% 16`, not division. – abligh Mar 20 '15 at 21:42
1

@indiv The shift by 4 is sensible here as `x` is conceptually a BCD number with a decimal digit every _4_ bits. From a BCD standpoint, code is dividing by "10" not 16, shifting one BCD per loop. Maybe `x >>= BCD_DIGIT_WIDTH` might work work for you. – chux - Reinstate Monica Mar 20 '15 at 23:20

score 3 · Answer 3 · answered Mar 20 '15 at 23:33

For a digit to be invalid, it needs to be 10-15. That in turn means 8 + 4 or 8+2 - the low bit doesn't matter at all.

So:

long mask8 = value & 0x88888888;
long mask4 = value & 0x44444444;
long mask2 = value & 0x22222222;
return ((mask8 >> 2) & ((mask4 >>1) | mask2) == 0;

Slightly less obvious:

long mask8 = (value>>2);
long mask42 = (value | (value>>1);
return (mask8 & mask42 & 0x22222222) == 0;

By shifting before masking, we don't need 3 different masks.

score 2 · Answer 4 · edited May 23 '17 at 12:07

Inspired by @Mark Ransom

 bool invalid = (0x88888888 & (((value & 0xEEEEEEEE) >> 1) + (0x66666666 >> 1))) != 0;
 // or
 bool valid = !((((value & 0xEEEEEEEEu) >> 1) + 0x33333333) & 0x88888888);

Mask off each BCD digit's 1's place, shift right, then add 6 and check for BCD digit overflow.

How this works:
By adding +6 to each digit, we look for an overflow * of the 4-digit sum.

 abcd
+ 110
-----
*efgd

But the bit value of d does not contribute to the sum, so first mask off that bit and shift right. Now the overflow bit is in the 8's place. This all is done in parallel and we mask these carry bits with 0x88888888 and test if any are set.

 0abc
+  11
-----
 *efg

8-digit BCD check

4 Answers4