Vocabulary/bdot

From J Wiki
Jump to navigation Jump to search

>> <<   Back to: Vocabulary Thru to: Dictionary

(m b.) y x (m b.) y Boolean/Bitwise/Bitwise Shift Adverb

Rank Infinity -- operates on [x and] y as a whole -- WHY IS THIS IMPORTANT?


Creates a verb to perform logic on the bit(s) of y (and x, if present).

The operand m (an integer) selects the appropriate logic to apply, according to this table:

For m ... The value of x must fit in: The value of y must fit in: Action
_16 to _1 boolean boolean (same as m+16)
0 to 15 boolean boolean logical function: x F y
16 to 31 integer integer bitwise logical function: x L y
32 integer integer left-rotate bits of y by x positions
33 integer integer (unsigned) left-shift bits of y by x positions
34 integer integer (signed) left-shift bits of y by x positions

Notes on the above table:

    • (monad) (m b.)y is the same as (dyad) x(m b.)y with x=0
    • To shift (or rotate) right instead of left, use a negative value for x
    • Left shift fills the vacated positions with 0
    • (Unsigned) right shift fills the vacated positions with 0
    • (Signed) right shift fills the vacated positions by the value (0|1) of the sign bit.

Examples:

1. Create the logical function of x and y which has its truth table encoded by the number m=2

   xandnoty =: 2 b.         NB. m=2 gives logical function: (x and not-y)
   0 1 0 1 xandnoty 0 0 1 1
0 1 0 0

Note[1]: To encode the truth table t into an integer m, ravel t and treat it as a binary numeral

   ] t=: 2 2 $ 0 0 1 0      NB. sample truth table: (x and not-y)
0 0
1 0

   ] m=: #. , t             NB. encode truth table t into an integer m
2

   ] m=: 2b0010             NB. or write m directly in base 2
2

   ] m=: 2b10010            NB. add 16 for the bitwise verbs
18

Note[2]: To verify the truth table corresponding to a given choice of integer m, use table to show truth table of the created logical function

   ] m =: 2b0010            NB. ravel of desired truth table: 0 0 ,: 1 0
2
   xandnoty =: m b.         NB. create corresponding logical fn

   0 1 xandnoty table 0 1
+--------+---+
|xandnoty|0 1|
+--------+---+
|0       |0 0|
|1       |1 0|
+--------+---+

table is a

  • Standard Library word(s) residing in the 'z'-locale
  • Defined in the factory script stdlib.ijs which is located in  ~system/main/stdlib.ijs
  • View the definition(s) in a JQt session by entering:  open '~system/main/stdlib.ijs'

2 Create a bitwise logical function (here, x and not-y) that independently combines corresponding bits of x and y

   xandnotybw =: 18 b.              NB. (m=16+2) same as (m=2) but combines integers x and y bitwise
   showbin =: '01' {~ (32#2)&#:     NB. verb to display (list of) integers as (table of) bits

   showbin 12 5 , (12 xandnotybw 5)
00000000000000000000000000001100
00000000000000000000000000000101
00000000000000000000000000001000

3. Create a verb to perform rotate left or shift left on the bits of integer y

   y=: _12345                       NB. non-trivial bit pattern with sign-bit set to 1
   showbin y , 4 (32 b.) y          NB. (m=32) - rotate left 4 places
11111111111111111100111111000111
11111111111111001111110001111111
   showbin y , _4 (33 b.) y         NB. (m=33) unsigned shift-right 4 places
11111111111111111100111111000111
00001111111111111111110011111100
   showbin y , _4 (34 b.) y         NB. signed shift-right 4 places
11111111111111111100111111000111
11111111111111111111110011111100

Note: shift-right 4 places is: shift-left _4 places.


Common Uses

1. Construct a logical verb (e.g. xor) from its truth table

but xor already has a J primitive: ~: . See below: More Information [1])

   ] m =: 2b0110            NB. from ravel of desired truth table: 0 1 ,: 1 0
6
   xor =: m b.              NB. create corresponding logical fn

   0 1 xor table 0 1        NB. verify truth table of xor
+---+---+
|xor|0 1|
+---+---+
|0  |0 1|
|1  |1 0|
+---+---+

2. Find the largest power of 2 that divides a given number, e.g. 448

   (17 b. -) 448                    NB. y BITWISE_AND (-y) gives the required result
64

3. Implement CRC polynomials using bit-shifting.


More Information

1. Every logical function has an equivalent J primitive.

m Equivalent m Equivalent m Equivalent m Equivalent
0 0"0 4 x < y 8 x +: y (NOR) 12 -. x
1 x *. y (AND) 5 y 9 x = y (XNOR) 13 x <: y
2 x > y 6 x ~: y (XOR) 10 -. y 14 x *: y (NAND)
3 x 7 x +. y (OR) 11 x >: y 15 1"0

Note: the primitive equivalents are faster than (m b.)

2. Operand m may be an array, in which case each result cell will be the array of the results of the logical functions specified by m.


Use These Combinations

Combinations using  b. y that have exceptionally good performance include:

What it does Type;

Precisions;
Ranks

Syntax Variants;

Restrictions

Benefits;

Bug Warnings

Integer reductions on infixes integer x (17 b.)/\ y also (22 b.) (23 b.) (25 b.) in place of (17 b.) much faster than alternatives
Integer reductions on partitions integer x (17 b.)//. y (22 b.) (23 b.) (25 b.) in place of (17 b.) avoids building argument cells
Polynomial Multiplication (bitwise) integer x (22 b.)//.@(17 b./) y avoids building argument cells
Bitwise reductions along diagonals integer (17 b.)//. y (22 b.) (23 b.) in place of (17 b.) avoids building argument cells
Integer [quotient/]remainder of power of 2 integer x | y with x a power of 2 If x is positive, (-x) 17 b. y is better to get remainder
Bitwise reduction and scan integer x (m b.)/ y

m is 16 to 31

/\ /\. in place of / much faster than alternatives
Bitwise operations on bytes byte u&.(a.&i.) y (u y) -: u"0 y avoids conversion to integer
(m b.)/&.(a.&i.) y

x (m b.)&.(a.&i.) y

m is 16 to 31