Essays/Bitwise Functions on Characters

From J Wiki
Jump to navigation Jump to search

m b. for m e. 16+i.16 computes bitwise functions on (machine-word) integers, whence m b.&.(a.&i.) computes bitwise functions on characters.

Problem: suppose y is computed in one of two ways:

y=: (c{a.) m b.&.(a.&i.) a.
y=: a.     m b.&.(a.&i.) c{a.

where c is an integer between 0 and 255. Given y , compute integers c1 and m1 such that

y -: (c1{a.) m1 b.&.(a.&i.) a.

The problem can be solved as follows:

f1=: 3 : 0 " 1
 'i j'=. a.i.0 255{y
 q=. _2 ]\ 0,j,  i,i,  i,255, i,(255-i), i,0,  255,j
 p=. _2 ]\ j,17, i,19, i,23,  i,22,      i,18, j,27
 p {~ q i. i,j
)

f2=: 3 : 0 " 1
 assert. ((,256)-:$y) *. 2=3!:0 y
 'i j'=. a.i.0 255{y
 if.     i=0     do. cm=. j,17
 elseif. j=i     do. cm=. i,19
 elseif. j=255   do. cm=. i,23
 elseif. j=255-i do. cm=. i,22
 elseif. j=0     do. cm=. i,18
 elseif. i=255   do. cm=. j,27
 elseif. 1       do. assert. 0 [ 'y is not generated by m b.' end.
 assert. y -: (c{a.) m b.&.(a.&i.) a. [ 'c m'=. cm
)

f1 and f2 are equivalent; f2 is less concise than f1 but incorporates checks and is more readily translated into a lower-level language. If y is not a result of m b. , then an error is signalled.

Examples:

   ] 'c m'=: 0 16+?256 16
110 19
   y=: (c{a.) m b.&.(a.&i.) a.
   f2 y
110 19
   y -: (110{a.) 19 b.&.(a.&i.) a.
1

   ] 'c m'=: 0 16+?256 16
54 25
   y=: a. m b.&.(a.&i.) c{a.
   f2 y
201 22
   y -: (201{a.) 22 b.&.(a.&i.) a.
1

   f1 a.{~ ?~ 256
|index error: f1
|   p    {~q i.i,j

   f2 a.{~ ?~ 256
|assertion failure: f2
|   0['y is not generated by m b.'

Test all possibilities:

   ya=: (16+i.16) 4 : 'y  x b.&.(a.&i.) a.'"0/ a.
   ay=: (16+i.16) 4 : 'a. x b.&.(a.&i.) y '"0/ a.

   $ ya
16 256 256
   $ ay
16 256 256

   1 [ f2 ya
1
   1 [ f2 ay
1

   (f1 -: f2) ya
1
   (f1 -: f2) ay
1

The choice of 0 255 as the y entries to use in the decision process is not unique. In fact, as the following expressions demonstrate, any pair i,255-i would do.

   t=: ya ,&(,/) ay    NB. all possibilities
   $ t
8192 256
   # ~. t              NB. # of all unique possibilities
1528
   # ~. 0 255{"1 t     NB. 0 255 capture them all
1528

   j=: (,.|.) i.256    NB. all pairs i,255-i

   *./ 1528 = j #@~.@({"1"_)"1 _ t
1



Contributed by Roger Hui. An earlier version of the text appeared in the J Forum on 2007-10-22.