Test int set bit and hex to long conversion functions

[DonovanHide]

Hi,

I've hit a blocker where I need to test for set bits in an int column that stores flags for an account. kdb doesn't seem to have built in bitwise operators. I've seen some blog posts about adding such functionality with linked in C libraries. Does anyone have a function in q which can do the same thing? 

Also slightly related, does anyone have a 8 byte hex string to long function? Obviously the fact that all kdb types are signed makes it a bit more complex...

Thanks for any help!

Cheers,

Donovan.

[rahul_asati04]

You need to write your own function to check set bits.  One way of doing that is to convert int to bit vector and check 1 in that:

q)  where 0b vs 5  

29 31

[keevey]

To convert hex string, first convert to byte vector and then use 1: (enlist"j";enlist 8)1:"X"$2 cut "abcdabcd01234567" http://code.kx.com/wiki/Reference/OneColon Sean

[DonovanHide]

Rahul and Sean, thank you very much! Most helpful mailing list ever 🙂

Any thoughts on the performance of these two variants of test bit (with the bit specified rising from least significant bit first)?

q)testb:{v:0b vs x;v[(count v)-(1+y)]}

q)testb2:{v:0b vs x;n:(count v)-(1+y);n in where v}

q)testb[5;2]

1b

q)testb2[5;2]

1b

Is there a function to get the bit or byte length of a type to avoid the count, or is count a fast operation anyway?

Thanks again!

[ikorkhov]

> Is there a function to get the bit or byte length of a type to avoid the count, or is count a fast operation anyway?

You can find sizes of all primitive types here: http://code.kx.com/wiki/Reference/Datatypes

[DonovanHide]

Hi Igor, yes I'm aware of standard datatype lengths 🙂

Just wanted to make the function general without lots of conditionals:

q)testb:{v:0b vs x;v[(count v)-(1+y)]}

q)testb[5h;0]

1b

q)testb[5j;0]

1b

q)testb[5i;0]

1b

The generality comes from using count on the bit vector. Just wondered if there was another way based on the type of x without lots of $ conditionals?

Cheers!

[ikorkhov]

> Any thoughts on the performance [...]

Well, you might have noticed band[] and bor[] are slow. Very slow:

band:{ 2 sv (0b vs x) & 0b vs y }

bor:{ 2 sv (0b vs x) | 0b vs y }

t:([]v: 1000000?256)

q)\t exec count i from t where v < 42 / simple comparison

11

q)\t exec count i from t where 37 = band'[v; 42]

12638

Three orders of magnitude slower than simple arithmetic test! But we could do better. The bottleneck here is 2 sv X, but when testing whether a flag is set or not we don't really need to compute a decimal value of and. So:

allset:{[v; mask] m ~/: (0b vs' v) &\: m:0b vs mask} / true if all flags specified by mask are set

anyset:{[v; mask] any each (0b vs' v) &\: 0b vs mask } / true if any flag is set

q)\t exec count i from t where allset[v; 42]

473

A bit better, but still significantly slower than our initial arithmetic example. But the good news is that if we have not too many flags, say 8, we could pre-compute x and y for all 0 <= x, y <= 255:

xand:v!band .''v,/:\:v:til 256 / xand[x; y] ~ x AND y

Using this dictionary we can select much faster:

q)\t exec count i from t where 42=xand[v; 42]

79

q)\t exec count i from t where 0<xand[v; 42]

82

Much better!

Hope this helps.

[DonovanHide]

Hi Igor, thanks! I will put that revised version through its paces 🙂

There are a maximum of 8 flag bits per flag so I should be ok:

https://github.com/rubblelabs/ripple/blob/master/data/flags.go#L51-L73

Does seem a shame that a single machine code instruction has to be so elaborately reconstructed, but kudos for doing so!

[ikorkhov]

You can define your own functions like this, for example:

band:{ 2 sv (0b vs x) & 0b vs y }

bor:{ 2 sv (0b vs x) | 0b vs y }

band[31;32] / returns 0

bor[31;32]  / returns 63

[DonovanHide]

Igor, thanks! That's actually more useful, in that it lets me test multiple flags/bits at once. Much appreciated.

Out of interest, does anyone know why q doesn't have integer bitwise operators built in? Keyword parsimony?