Hex Byte and multiple of 10

NETMF & Gadgeteer
1

Hi everyone

I am try to code a really a dummy thing. This sould be easy but I am not satisfy with my solution and I am sure that I miss something here…
Here’s the problem:
I am receiving message over can bus and would like to check if the first byte is a multiple of ten:
80
81
82
83
The solution should return true only for the first item.

It should also support this:
A0
A1
A2
A3

I am actually doing the conversion of byte to HEX string and check if the second char is 0 or not. It seems to me that this is not efficient in terms of runtime and memory.

Any idea?

2

yes you’re right… this will be better…

Checking bit 1 2 3 4 would do the job

3

Maybe modulo … if (hexbyte % 0x10) …

1 Like
4

@ RobvanSchelven - I already write the code like this:

  
if ((_msgList[i].Data[0] & 1) == 0 && (_msgList[i].Data[0] & 2) == 0 && (_msgList[i].Data[0] & 4) == 0 && (_msgList[i].Data[0] & 4) == 0)

I am wondering what would be the faster…

5

@ andre.m -

using System;
using Microsoft.SPOT;

namespace testmod
{
    public class Program
    {
        public static void Main()
        {
            Debug.Print(Resources.GetString(Resources.StringResources.String1));
            var r = new Random();
            byte[] bs = new byte[2000];
            r.NextBytes(bs);
            int count = 0;
            int count2 = 0;
            DateTime start = DateTime.Now;
            for (int i=0;i<1000;i++)
                if ((bs[i] & 1) == 0 && (bs[i] & 2) == 0 && (bs[i] & 4) == 0 && (bs[i] & 8) == 0)
                {
                    count++;
                }
            Debug.Print("Check bits: " + (DateTime.Now - start).Ticks / 10 + ", micro seconds");
            start = DateTime.Now;
            for (int i = 0; i < 1000; i++)
            {
                if ((bs[i]%0x10) == 0)
                {
                   count2++ ;
                }
            }
            Debug.Print("Check modulo: " + (DateTime.Now - start).Ticks / 10 + ", micro seconds");
            Debug.Print(count.ToString() +"\t"+ count2.ToString());
        }
    }
}

Modulo is faster… :open_mouth:

6

@ leforban : something is strange in your code sample… In the first post you say that you want to know if a number is a multiple of ten and in your code sample you are checking if it is a multiple of sixteen (0x10) :open_mouth:

If you really want to test for a multiple of 16, then there is a faster operation : logical AND

start = DateTime.Now;
            for (int i = 0; i < 1000; i++)
            {
                if ((bs[i] & 0x0F) == 0)    // 0x10 - 1
                {
                    count3++;
                }
            }
            Debug.Print("Check AND: " + (DateTime.Now - start).Ticks / 10 + ", micro seconds");

And this is working for any modulus operator that is a power of two.

I will let you publish (or not) the results because I do not have the same timings as you for the same code :

Check bits: 16020, micro seconds
Check modulo: 16340, micro seconds
Check AND: 15771, micro seconds
61 61 61

It seems that the modulus is slower in my case but it is not if I use 10 000 numbers in the array :
Check bits: 171012, micro seconds
Check modulo: 163257, micro seconds
Check AND: 157237, micro seconds
633 633 633

But in every case, the logical AND method is faster. Again : only with modulus operator being a power of 2.

7

done! In fact I had already tried modulo operator but with %10 instead of %0x10 which was returning wrong results…

His solution is better in terms of runtime and make the code easier to read!

8

@ leforban - If you testing it on a hardware I wonder what time this test will show


for (int i = 0; i < 1000; i++)
{
  if( (bs[i] == 0) || (15 == (((uint)bs[i] * 0x19999999) >> 28)))
  {
      count3++;
  }
}

P.S. If your byte is always non-zero the first check ( bs[I] == 0 ) can be removed and it should be faster.

9

@ Bec a Fuel - You’re right this is not multiple of ten, but sixteen… and even it has to return true for 0x00…

For information it is used in the Fast Packet protocol for NMEA2K and SAEj1939.

10

@ Architect - It can be 00. However I do not understand the aim of your code :open_mouth:

11

@ leforban - it does what you have asked. Checks if a byte is a multiple of 10. :wink:

12

I feel like I am taking crazy pills.

Isn’t the standard, best-practice way to determine if a value is a multiple of 16 simply to and the lowest byte with 0x0F and check if it is non-zero?

Is there truly a debate? Is there something more efficient? I’ve been doing it that way for more than 30 years.

And don’t listen to Architect (this time, anyway) - he’s trying to mess with you :slight_smile:

13

mtylerjr wrote “Isn’t the standard, best-practice way to determine if a value is a multiple of 16”

The question was not about a multiple of 16, but about a multiple of 10

14

Okay, but (100 * 0x19999999) >> 28 == 0, not 15

… unless he is exploiting some hardware precision deficiency?

15

It is in unsigned world :wink:

(b[/b](100 * 0x19999999) >> 28 ) == 15

16

@ Architect -

Okay, I see what’s going on. :slight_smile:

I hope you never use that in production code though, lol.

17

It is perfectly safe. We launched Sputnik using that formula ;D ;D ;D

2 Likes
18

Guys, you are scaring me !

19

@ leforban, @ mtylerjr - The idea behind the formula is actually simple.

We want to find n mod 10
Or in the following form: n = 10k+r, 0 <= r <= 9 We want to find: r
Finding a mod of a number that is power of 2 is very trivial and cheap operation, but 10 is not. Let’s take a look at a different function:
16n/10 mod 16
Let’s open it up and simplify:
16(10k+r)/10 mod 16 = (16k + 16r/10) mod 16 = 16r/10 mod 16
Now if we use the possible values of r=[0…9] and calculate 16r/10 mod 16. We will get back 10 distinct values:
0, 1, 3, 4, 6, 8, 9,11, 12, 14 for r = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 respectively.

Back to 16n/10 mod 16. If we find an easy way to compute that function we can easily map it to mod 10 reminder using the above results. We can use an approximation this way: multiply n by b/10[/b] and then divide it by 2^28.
0x19999999 is a floor value of b/10[/b] in hex and division by 2^28 is the same as right shift by 28.

((uint)(n * 0x19999999) >> 28 )

Due to approximation the final values are slightly different and 0 is a special case (n=0 returns 0, all other n where r = 0 return 15), but they are still distinct and can be mapped to mod 10 reminder.

P.S. If we treat the result as an index in a lookup table for the reminder. We can use this table:
mod10reminder[16] = { 0, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7, 7, 8, 8, 9, 0};

This whole magic comes from:
Hacker’s Delight (2nd Edition)

1 Like
20

Here’s the results on G400D

Check bits: 46065, micro seconds
Check modulo: 34907, micro seconds
Check formula: 52905, micro seconds

modulo operator seems better for this purpose