git.iko.soy/urbit.org
on c19bc7a help sign in
urbit.org/docs/reference/library/2c.udon
1254 lines 16 kB history raw
1:- :~ navhome/'/docs/'
2 sort/'6'
3 title/'2c: Bit Arithmetic'
4 ==
6;>
8# 2c: bit arithmetic
10### `++bex`
12Binary exponent
14Computes the result of `2^a`, producing an atom.
16#### Accepts
18`a` is an atom.
20#### Produces
22An atom.
24#### Source
26```
27 ++ bex
28 ~/ %bex
29 |= a=@
30 ^- @
31 ?: =(0 a) 1
32 (mul 2 $(a (dec a)))
33```
35#### Examples
37```
38 > (bex 4)
39 16
41 > (bex (add 19 1))
42 1.048.576
44 > (bex 0)
45 1
46```
48---
49### `++can`
51Assemble
53Produces an atom from a list `b` of length-value pairs `p` and `q`,
54where `p` is the length in blocks of size `a`, and `q` is an atomic
55value.
57#### Accepts
59`a` is a block size (see [`++bloq`](../1c)).
61`b` is a `list` of length-value pairs, `p` and `q`.
63#### Produces
65An atom.
67#### Source
69```
70 ++ can
71 ~/ %can
72 |= [a=bloq b=(list [p=@ q=@])]
73 ^- @
74 ?~ b 0
75 (add (end a p.i.b q.i.b) (lsh a p.i.b $(b t.b)))
76```
78#### Examples
80```
81 > `@ub`21 :: @ub is the binary aura
82 0b1.0101
84 > `@ub`(can 3 ~[[1 21]])
85 0b1.0101
87 > `@ub`(can 3 ~[[1 1]])
88 0b1
90 > `@ub`(can 0 ~[[1 255]])
91 0b1
93 > `@ux`(can 3 [3 0xc1] [1 0xa] ~) :: @ux is the hexadecimal aura
94 0xa00.00c1
96 > `@ux`(can 3 [3 0xc1] [1 0xa] [1 0x23] ~)
97 0x23.0a00.00c1
99 > `@ux`(can 4 [3 0xc1] [1 0xa] [1 0x23] ~)
100 0x23.000a.0000.0000.00c1
102 > `@ux`(can 3 ~[[1 'a'] [2 'bc']])
103 0x63.6261
104```
106---
107### `++cat`
109Concatenate
111Concatenates two atoms, `b` and `c`, according to block size `a`, producing an
112atom.
114#### Accepts
116`a` is a block size (see [`++bloq`](../1c)).
118`b` is an atom.
120`c` is an atom.
122#### Produces
124An atom.
126#### Source
128```
129 ++ cat
130 ~/ %cat
131 |= [a=bloq b=@ c=@]
132 (add (lsh a (met a b) c) b)
133```
135#### Examples
137```
138 > `@ub`(cat 3 1 0) :: @ub is the binary aura
139 0b1
141 > `@ub`(cat 0 1 1)
142 0b11
144 > `@ub`(cat 0 2 1)
145 0b110
147 > `@ub`(cat 2 1 1)
148 0b1.0001
150 > `@ub`256
151 0b1.0000.0000
153 > `@ub`255
154 0b1111.1111
156 > `@ub`(cat 3 256 255)
157 0b1111.1111.0000.0001.0000.0000
159 > `@ub`(cat 2 256 255)
160 0b1111.1111.0001.0000.0000
162 > (cat 3 256 255)
163 16.711.936
165 > (cat 2 256 255)
166 1.044.736
167```
169---
170### `++cut`
172Slice
174Slices `c` blocks of size `a` that are positioned `b` blocks from the end of
175`d`. That slice is produced as an atom.
177#### Accepts
179`a` is a block size (see [`++bloq`](../1c)).
181`b` is an atom.
183`c` is an atom.
185`d` is an atom.
187#### Produces
189An atom.
191#### Source
193```
194 ++ cut
195 ~/ %cut
196 |= [a=bloq [b=@u c=@u] d=@]
197 (end a c (rsh a b d))
198```
200#### Examples
202```
203 > (cut 0 [1 1] 2)
204 1
206 > (cut 0 [2 1] 4)
207 1
209 > `@t`(cut 3 [0 3] 'abcdefgh')
210 'abc'
212 > `@t`(cut 3 [1 3] 'abcdefgh') :: @t is the cord aura
213 'bcd'
215 > `@ub`(cut 0 [0 3] 0b1111.0000.1101) :: @ub is the binary aura
216 0b101
218 > `@ub`(cut 0 [0 6] 0b1111.0000.1101)
219 0b1101
221 > `@ub`(cut 0 [4 6] 0b1111.0000.1101)
222 0b11.0000
224 > `@ub`(cut 0 [3 6] 0b1111.0000.1101)
225 0b10.0001
226```
229---
230### `++end`
232Tail
234Produces an atom by taking the last `b` blocks of size `a` from `c`.
236#### Accepts
238`a` is a block size (see [`++bloq`](../1c)).
240`b` is an atom.
242`c` is an atom.
244#### Produces
246An atom.
249#### Source
251```
252 ++ end
253 ~/ %end
254 |= [a=bloq b=@u c=@]
255 (mod c (bex (mul (bex a) b)))
256```
258#### Examples
260```
261 > (end 2 2 255)
262 255
264 > (end 3 1 255)
265 255
267 > (end 3 1 256)
268 0
270 > `@ub`12 :: @ub is the binary aura
271 0b1100
273 > `@ub`(end 0 3 12)
274 0b100
276 > (end 0 3 12)
277 4
279 > `@ub`(end 1 3 12)
280 0b1100
282 > (end 1 3 12)
283 12
285 > `@ux`'abc' :: @ux is the hexademical aura
286 0x63.6261
288 > `@ux`(end 3 2 'abc')
289 0x6261
291 > `@t`(end 3 2 'abc') :: @t is the cord aura
292 'ab'
293```
296---
297### `++fil`
299Fill bloqstream
301Produces an atom by repeating `c` for `b` blocks of size `a`.
303#### Accepts
305`a` is a block size (see [`++bloq`](../1c)).
307`b` is an atom.
309`c` is an atom.
311#### Produces
313An atom.
315#### Source
317```
318 ++ fil
319 |= [a=bloq b=@u c=@]
320 =+ n=0
321 =+ d=c
322 |- ^- @
323 ?: =(n b)
324 (rsh a 1 d)
325 $(d (add c (lsh a 1 d)), n +(n))
326```
328#### Examples
330```
331 > `@t`(fil 3 5 %a) :: @t is the cord (string) aura
332 'aaaaa'
334 > `@t`(fil 5 10 %ceeb)
335 'ceebceebceebceebceebceebceebceebceebceeb'
337 > `@t`(fil 4 10 %eced)
338 'ʇʇʇʇʇʇʇʇʇʇed'
340 > `@tas`(fil 4 10 %bf) :: @tas is the term aura
341 %bfbfbfbfbfbfbfbfbfbf
343 > `@ub`(fil 2 6 1) :: @ub is the binary aura
344 0b1.0001.0001.0001.0001.0001
345```
348---
349### `++lsh`
351Left-shift
353Produces an atom by left-shifting `c` by `b` blocks of size `a`.
355#### Accepts
357`a` is a block size (see [`++bloq`](../1c)).
359`b` is an atom.
361`c` is an atom.
363#### Produces
365An atom.
367#### Source
369```
370 ++ lsh
371 ~/ %lsh
372 |= [a=bloq b=@u c=@]
373 (mul (bex (mul (bex a) b)) c)
374```
376#### Examples
378```
379 > `@ub`1 :: @ub is the binary aura
380 0b1
382 > `@ub`(lsh 0 1 1)
383 0b10
385 > (lsh 0 1 1)
386 2
388 > `@ub`255
389 0b1111.1111
391 > `@ub`(lsh 3 1 255)
392 0b1111.1111.0000.0000
394 > (lsh 3 1 255)
395 65.280
396```
399---
400### `++met`
402Measure
404Computes the number of blocks of size `a` in `b`, producing an atom.
406#### Accepts
408`a` is a block size (see [`++bloq`](../1c)).
410`b` is an atom.
412#### Source
414```
415 ++ met
416 ~/ %met
417 |= [a=bloq b=@]
418 ^- @
419 =+ c=0
420 |-
421 ?: =(0 b) c
422 $(b (rsh a 1 b), c +(c))
423```
425#### Examples
427```
428 > (met 0 1)
429 1
431 > (met 0 2)
432 2
434 > (met 3 255)
435 1
437 > (met 3 256)
438 2
440 > (met 3 'abcde')
441 5
442```
445---
446### `++rap`
448Assemble non-zero
450Concatenates a list of atoms `b` using block size `a`, producing an atom.
452#### Accepts
454`a` is a block size (see [`++bloq`](../1c)).
456`b` is a `list` of atoms.
458#### Produces
460An atom.
462#### Source
464```
465 ++ rap
466 ~/ %rap
467 |= [a=bloq b=(list @)]
468 ^- @
469 =+ ~
470 ?~ b 0
471 (cat a i.b $(b t.b))
472```
474#### Examples
476```
477 > `@ub`(rap 2 [1 2 3 4 ~]) :: @ub is the binary aura
478 0b100.0011.0010.0001
480 > `@ub`(rap 1 [1 2 3 4 ~])
481 0b1.0011.1001
483 > (rap 0 [0 0 0 ~])
484 0
486 > (rap 0 [1 0 1 ~])
487 3
489 > `@ub`3
490 0b11
492 > (rap 0 [0 1 0 0 1 2 ~])
493 11
495 > (rap 0 [1 1 2 ~])
496 11
498 > `@ub`11
499 0b1011
500```
502#### Discussion
504Any element of the value `0` is not included in concatenation.
506---
507### `++rep`
509Assemble single
511Produces an atom by assembling a list of atoms `b` using block size `a`.
513#### Accepts
515`a` is a block size (see [`++bloq`](../1c)).
517`b` is a list of atoms.
519#### Produces
521An atom.
523#### Source
525```
526 ++ rep
527 ~/ %rep
528 |= [a=bloq b=(list @)]
529 ^- @
530 =+ c=0
531 |-
532 ?~ b 0
533 (add (lsh a c (end a 1 i.b)) $(c +(c), b t.b))
534```
536#### Examples
538```
539 > `@ub`(rep 2 [1 2 3 4 ~]) :: @ub is the binary aura
540 0b100.0011.0010.0001
542 > (rep 0 [0 0 1 ~])
543 4
545 > (rep 0 [0 0 0 1 ~])
546 8
548 > `@ub`(rep 0 [0 0 0 1 ~])
549 0b1000
551 > `@ub`8
552 0b1000
554 > (rep 0 [0 1 0 0 ~])
555 2
557 > (rep 0 [0 1 0 1 ~])
558 10
560 > (rep 0 [1 0 1 0 1 ~])
561 21
563 > `@ub`21
564 0b10.1010
566 > `@ub`(rep 3 [12 166 8 34 ~])
567 0b10.0010.0000.1000.1010.0110.0000.1100
568```
571---
572### `++rip`
574Disassemble
576Produces a list of atoms from the bits of `b` using block size `a`.
578#### Accepts
580`a` is a block size (see [`++bloq`](../1c)).
582`b` is an atom.
584#### Produces
586A list of atoms.
588#### Source
590```
591 ++ rip
592 ~/ %rip
593 |= [a=bloq b=@]
594 ^- (list @)
595 ?: =(0 b) ~
596 [(end a 1 b) $(b (rsh a 1 b))]
597```
599#### Examples
601```
602 > `@ub`155 :: @ub is the binary aura
603 0b1001.1011
605 > (rip 0 155)
606 ~[1 1 0 1 1 0 0 1]
608 > (rip 2 155)
609 ~[11 9]
611 > (rip 0 11)
612 ~[1 1 0 1]
614 > (rip 1 155)
615 ~[3 2 1 2]
617 > `@ub`256
618 0b1.0000.0000
620 > (rip 0 256)
621 ~[0 0 0 0 0 0 0 0 1]
623 > (rip 2 256)
624 ~[0 0 1]
626 > (rip 3 256)
627 ~[0 1]
628```
631---
632### `++rsh`
634Right-shift
636Right-shifts `c` by `b` blocks of size `a`, producing an atom.
638#### Accepts
640`a` is a block size (see [`++bloq`](../1c)).
642`b` is an atom.
644`c` is an atom.
646#### Produces
648An atom.
650#### Source
652```
653 ++ rsh
654 ~/ %rsh
655 |= [a=bloq b=@u c=@]
656 (div c (bex (mul (bex a) b)))
657```
659#### Examples
661```
662 > `@ub`145 :: @ub is the binary aura
663 0b1001.0001
665 > `@ub`(rsh 1 1 145)
666 0b10.0100
668 > (rsh 1 1 145)
669 36
671 > `@ub`(rsh 2 1 145)
672 0b1001
674 > (rsh 2 1 145)
675 9
677 > `@ub`10
678 0b1010
680 > `@ub`(rsh 0 1 10)
681 0b101
683 > (rsh 0 1 10)
684 5
686 > `@ux`'abc'
687 0x63.6261
689 > `@t`(rsh 3 1 'abc')
690 'bc'
692 > `@ux`(rsh 3 1 'abc')
693 0x6362
694```
697---
698### `++swp`
700Reverse block order
702Switches little-endian to big-endian and vice versa: produces an atom by
703reversing the block order of `b` using block size `a`.
706#### Accepts
708`a` is a block size (see [`++bloq`](../1c)).
710`b` is an atom.
712#### Produces
714An atom
716#### Source
718```
719 ++ swp |=([a=bloq b=@] (rep a (flop (rip a b))))
720```
722#### Examples
724```
725 > `@ub`24 :: @ub is the binary aura
726 0b1.1000
728 > (swp 0 24)
729 3
731 > `@ub`3
732 0b11
734 > (swp 0 0)
735 0
737 > (swp 0 128)
738 1
739```
742---
743### `++xeb`
745Binary logarithm
747Computes the base-2 logarithm of `a`, producing an atom.
749#### Accepts
751`a` is an atom.
753#### Produces
755An atom.
757#### Source
759```
760 ++ xeb
761 ~/ %xeb
762 |= a=@
763 ^- @
764 (met 0 a)
765```
767#### Examples
769```
770 > (xeb 31)
771 5
773 > (xeb 32)
774 6
776 > (xeb 49)
777 6
779 > (xeb 0)
780 0
782 > (xeb 1)
783 1
785 > (xeb 2)
786 2
787```
790---
791### `++fe`
793Modulo bloq
795Core that contains arms for `bloq` and modular integer operations.
797#### Accepts
799`a` is a `bloq`.
801#### Source
803```
804 |_ a=bloq
805```
807---
808### `++dif`
810Produces the difference between two atoms in the modular basis
811representation.
813#### Accepts
815`a` is a `bloq`.
817`b` is an atom.
819`c` is an atom.
821#### Produces
823A `@s`
825#### Source
827```
828 ++ dif |=([b=@ c=@] (sit (sub (add out (sit b)) (sit c))))
829```
831#### Examples
833```
834 > (~(dif fe 3) 63 64)
835 255
837 > (~(dif fe 3) 5 10)
838 251
840 > (~(dif fe 3) 0 1)
841 255
843 > (~(dif fe 0) 9 10)
844 1
846 > (~(dif fe 0) 9 11)
847 0
849 > (~(dif fe 0) 9 12)
850 1
852 > (~(dif fe 2) 9 12)
853 13
855 > (~(dif fe 2) 63 64)
856 15
857```
859---
860### `++inv`
862Inverse
864Inverts the order of the modular field.
866#### Accepts
868`b` is a `bloq`. (see [`++bloq`](../1c))
870#### Produces
872An atom.
874#### Source
876```
877 ++ inv |=(b=@ (sub (dec out) (sit b)))
878```
880#### Examples
882```
883 > (~(inv fe 3) 255)
884 0
886 > (~(inv fe 3) 256)
887 255
889 > (~(inv fe 3) 0)
890 255
892 > (~(inv fe 3) 1)
893 254
895 > (~(inv fe 3) 2)
896 253
898 > (~(inv fe 3) 55)
899 200
900```
902---
903### `++net`
905Flip endianness
907Reverses bytes within a block.
909#### Accepts
911`b` is a `bloq`. (see [`++bloq`](../1c))
913#### Produces
915An atom.
917#### Source
919```
920 ++ net |= b=@ ^- @
921 => .(b (sit b))
922 ?: (lte a 3)
923 b
924 =+ c=(dec a)
925 %+ con
926 (lsh c 1 $(a c, b (cut c [0 1] b)))
927 $(a c, b (cut c [1 1] b))
928```
930#### Examples
932```
933 > (~(net fe 3) 64)
934 64
936 > (~(net fe 3) 128)
937 128
939 > (~(net fe 3) 255)
940 255
942 > (~(net fe 3) 256)
943 0
945 > (~(net fe 3) 257)
946 1
948 > (~(net fe 3) 500)
949 244
951 > (~(net fe 3) 511)
952 255
954 > (~(net fe 3) 512)
955 0
957 > (~(net fe 3) 513)
958 1
960 > (~(net fe 3) 0)
961 0
963 > (~(net fe 3) 1)
964 1
966 > (~(net fe 0) 1)
967 1
969 > (~(net fe 0) 2)
970 0
972 > (~(net fe 0) 3)
973 1
975 > (~(net fe 6) 1)
976 72.057.594.037.927.936
978 > (~(net fe 6) 2)
979 144.115.188.075.855.872
981 > (~(net fe 6) 3)
982 216.172.782.113.783.808
984 > (~(net fe 6) 4)
985 288.230.376.151.711.744
987 > (~(net fe 6) 5)
988 360.287.970.189.639.680
989```
991---
992### `++out`
994Max integer value
996Produces the maximum integer value that the current block can store; `2^a^a`.
998#### Accepts
1000`a` is a `bloq`.
1002#### Produces
1004An atom.
1006#### Source
1008```
1009 ++ out (bex (bex a))
1010```
1012#### Examples
1014```
1015 > ~(out fe 0)
1018 > ~(out fe 1)
1021 > ~(out fe 2)
1022 16
1024 > ~(out fe 3)
1025 256
1027 > ~(out fe 4)
1028 65.536
1030 > ~(out fe 10)
1031 \/179.769.313.486.231.590.772.930.519.078.902.473.361.797.697.894.230.657.273\/
1032 .430.081.157.732.675.805.500.963.132.708.477.322.407.536.021.120.113.879.87
1033 1.393.357.658.789.768.814.416.622.492.847.430.639.474.124.377.767.893.424.8
1034 65.485.276.302.219.601.246.094.119.453.082.952.085.005.768.838.150.682.342.
1035 462.881.473.913.110.540.827.237.163.350.510.684.586.298.239.947.245.938.479
1036 .716.304.835.356.329.624.224.137.216
1037 \/ \/
1038```
1040---
1041### `++rol`
1043Roll left
1045Rolls `d` to the left by `c` `b`-sized blocks.
1047#### Accepts
1049`a` is a `bloq`.
1051`b` is a `bloq`.
1053`c` is an atom.
1055`d` is an atom.
1057#### Produces
1059An atom.
1061#### Source
1063```
1064 ++ rol |= [b=bloq c=@ d=@] ^- @
1065 =+ e=(sit d)
1066 =+ f=(bex (sub a b))
1067 =+ g=(mod c f)
1068 (sit (con (lsh b g e) (rsh b (sub f g) e)))
1069```
1071#### Examples
1073```
1074 > `@ux`(~(rol fe 6) 4 3 0xabac.dedf.1213)
1075 0x1213.0000.abac.dedf
1077 > `@ux`(~(rol fe 6) 4 2 0xabac.dedf.1213)
1078 0xdedf.1213.0000.abac
1080 > `@t`(~(rol fe 5) 3 1 'dfgh')
1081 'hdfg'
1083 > `@t`(~(rol fe 5) 3 2 'dfgh')
1084 'ghdf'
1086 > `@t`(~(rol fe 5) 3 0 'dfgh')
1087 'dfgh'
1088```
1090---
1091### `++ror`
1093Roll right
1095Rolls `d` to the right by `c` `b`-sized blocks.
1097#### Accepts
1099`a` is a `bloq`.
1101`b` is a `bloq`.
1103`c` is an atom.
1105`d` is an atom.
1107#### Produces
1109An atom.
1111#### Source
1113```
1114 ++ ror |= [b=bloq c=@ d=@] ^- @
1115 =+ e=(sit d)
1116 =+ f=(bex (sub a b))
1117 =+ g=(mod c f)
1118 (sit (con (rsh b g e) (lsh b (sub f g) e)))
1119```
1121#### Examples
1123```
1124 > `@ux`(~(ror fe 6) 4 1 0xabac.dedf.1213)
1125 0x1213.0000.abac.dedf
1127 > `@ux`(~(ror fe 6) 3 5 0xabac.dedf.1213)
1128 0xacde.df12.1300.00ab
1130 > `@ux`(~(ror fe 6) 3 3 0xabac.dedf.1213)
1131 0xdf12.1300.00ab.acde
1133 > `@t`(~(rol fe 5) 3 0 'hijk')
1134 'hijk'
1136 > `@t`(~(rol fe 5) 3 1 'hijk')
1137 'khij'
1139 > `@t`(~(rol fe 5) 3 2 'hijk')
1140 'jkhi'
1141```
1143---
1144### `++sit`
1146Enforce modulo
1148Produces an atom in the current modular block representation.
1150#### Accepts
1152`a` is a `bloq`.
1154`b` is an atom.
1156#### Produces
1158An atom.
1160#### Source
1162```
1163 ++ sit |=(b=@ (end a 1 b))
1164```
1166#### Examples
1168```
1169 > (~(sit fe 3) 255)
1170 255
1172 > (~(sit fe 3) 256)
1175 > (~(sit fe 3) 257)
1178 > (~(sit fe 2) 257)
1181 > (~(sit fe 2) 10.000)
1184 > (~(sit fe 2) 100)
1187 > (~(sit fe 2) 19)
1190 > (~(sit fe 2) 17)
1193 > (~(sit fe 0) 17)
1196 > (~(sit fe 0) 0)
1199 > (~(sit fe 0) 1)
1201```
1203---
1205### `++sum`
1207Sum
1209Sums two numbers in this modular field.
1211#### Accepts
1213`a` is a `bloq`.
1215`b` is an atom.
1217`c` is an atom.
1219#### Produces
1221An atom.
1223#### Source
1225```
1226 ++ sum |=([b=@ c=@] (sit (add b c)))
1227```
1229#### Examples
1231```
1232 > (~(sum fe 3) 10 250)
1235 > (~(sum fe 0) 0 1)
1238 > (~(sum fe 0) 0 2)
1241 > (~(sum fe 2) 14 2)
1244 > (~(sum fe 2) 14 3)
1247 > (~(sum fe 4) 10.000 256)
1248 10.256
1250 > (~(sum fe 4) 10.000 100.000)
1251 44.464
1252```
1254---