Author Topic: bits...  (Read 1385 times)

0 Members and 1 Guest are viewing this topic.

ribarm

• Water Moccasin
• Posts: 2108
• Marko Ribar, architect
bits...
« on: February 02, 2019, 01:57:47 AM »
Hi... I've put this short sub for splitting integer into bits, but I am unsure is it correct for negative integers... I know (logand), (logior) functions work and for negative numbers, but I don't understand the logic behind... Any insight is welcome...

Code: [Select]
`;;; bits by M.R.(defun bits ( n / bit bitl rtn ) ;;; n - integer ; (bits 20000) => (32 512 1024 2048 16384) ; (bits -20000) => (-16384 -2048 -1024 -512 -32) ; (bits 0) => nil  (if (minusp n)    (progn      (setq bit -0.5)      (while (>= (setq bit (fix (* bit 2.0))) n)        (setq bitl (cons bit bitl))      )      (foreach bit (reverse bitl)        (if (= (logand (- bit) (- n)) (- bit))          (setq rtn (cons bit rtn))        )      )      rtn    )    (progn      (setq bit 0.5)      (while (<= (setq bit (fix (* bit 2.0))) n)        (setq bitl (cons bit bitl))      )      (foreach bit (reverse bitl)        (if (= (logand bit n) bit)          (setq rtn (cons bit rtn))        )      )      (reverse rtn)    )  ))`
M.R.
Marko Ribar, d.i.a. (graduated engineer of architecture)

M.R. on Youtube

roy_043

• Water Moccasin
• Posts: 1703
• BricsCAD 18
Re: bits...
« Reply #1 on: February 02, 2019, 03:54:10 AM »
-2000 represented as a 32-bit binary number:
11111111111111111111100000110000
The list your function returns should contain a number for every '1':
Code - Auto/Visual Lisp: [Select]
1. (defun KGA_Math_BitList (int)
2.     0
3.       '(lambda (idx) (lsh (lsh (lsh int (- 31 idx)) -31) idx))
4.       '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31)
5.     )
6.   )
7. )
(KGA_Math_BitList -2000) =>
(16 32 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 -2147483648)

Marc'Antonio Alessi

• Swamp Rat
• Posts: 988
• Marco
Re: bits...
« Reply #2 on: February 02, 2019, 05:14:34 AM »
Code: [Select]
`; Function: UtlBits_GetBitWise ; Credits: Juerg Menzi;; Version 1.00 - 16/11/2006;; Arguments:;   BtsVal = Integer [INT];; Return Values:;  [LIST] a list of all logical bitwise AND's of an integer;         or nil if BtsVal > 32767 or < 1;; Examples:;  (UtlBits_GetBitWise 32767);  ==> (1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384);  (UtlBits_GetBitWise 32768);  ==> nil;  (UtlBits_GetBitWise   nil);  ==> nil;  (UtlBits_GetBitWise     0);  ==> nil; (defun UtlBits_GetBitWise (BtsVal / CurBit OutVal)  (cond    ( (> 1 BtsVal 32767) nil ) ; 32767 = bits sum max value    ( (setq CurBit 1)      (while (<= CurBit BtsVal)        (if (= (logand BtsVal CurBit) CurBit)          (setq OutVal (cons CurBit OutVal))        )        (setq CurBit (* CurBit 2))      )      (reverse OutVal)    )  ))`

ribarm

• Water Moccasin
• Posts: 2108
• Marko Ribar, architect
Re: bits...
« Reply #3 on: February 02, 2019, 07:31:22 AM »
So... With help of Roy's sub, I figured out what is logic behing (logand) and (logior) :

Code - Auto/Visual Lisp: [Select]
1. (defun _bits ( int )
2.     0
3.       '(lambda ( idx ) (lsh (lsh (lsh int (- 31 idx)) -31) idx))
4.       '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31)
5.     )
6.   )
7. )
8.
9. (defun _int ( l1 l2 / rtn )
10.   (foreach x l1
11.     (if (vl-position x l2)
12.       (setq rtn (cons x rtn))
13.     )
14.   )
15.   (reverse rtn)
16. )
17.
18. (defun _uni ( l1 l2 / unique )
19.   (defun unique ( l )
20.     (if l
21.       (cons (car l)
22.         (unique (vl-remove (car l) l))
23.       )
24.     )
25.   )
26.   (unique (append l1 l2))
27. )
28.
29. (defun _logand ( i1 i2 )
30.   (apply '+ (_int (_bits i1) (_bits i2)))
31. )
32.
33. (defun _logior ( i1 i2 )
34.   (apply '+ (_uni (_bits i1) (_bits i2)))
35. )
36.

Thank you very much for your sub @Roy...
Regards...
Marko Ribar, d.i.a. (graduated engineer of architecture)

M.R. on Youtube

roy_043

• Water Moccasin
• Posts: 1703
• BricsCAD 18
Re: bits...
« Reply #4 on: February 02, 2019, 07:37:14 AM »
You may also want to look at the boole function.

Lee Mac

• Seagull
• Posts: 12241
• London, England
Re: bits...
« Reply #5 on: February 02, 2019, 09:04:17 AM »
Nice code Roy

Here are a couple of alternatives, using logand -
Code - Auto/Visual Lisp: [Select]
1. (defun bits ( n / b r )
2.     (repeat (setq b 32) (setq r (cons (logand n (lsh 1 (setq b (1- b)))) r)))
3.     (vl-remove 0 r)
4. )
Code - Auto/Visual Lisp: [Select]
1. (defun bits ( n )
2.     (if (/= 0 n) (vl-remove 0 (cons (logand 1 n) (mapcar '(lambda ( x ) (lsh x 1)) (bits (lsh n -1))))))
3. )
« Last Edit: February 02, 2019, 09:28:23 AM by Lee Mac »

Marc'Antonio Alessi

• Swamp Rat
• Posts: 988
• Marco
Re: bits...
« Reply #6 on: February 03, 2019, 05:06:10 AM »
Since it's a function I use very often I'm interested in being able to change it with a more efficient one.
Code: [Select]
`Benchmark.lsp | © 2005 Michael Puckett | All Rights ReservedElapsed milliseconds / relative speed for 65536 iteration(s):    (BITSJ1 32767)................1469 / 7.61 <fastest>    (BITSJ1 32767)................1485 / 7.52    (BITSMR 32767)................2031 / 5.5    (BITSMR 32767)................2062 / 5.42    (BITSL1 32767)................3047 / 3.67    (BITSL1 32767)................3047 / 3.67    (_BITS 32767).................4093 / 2.73    (KGA_MATH_BITLIST 32767)......4094 / 2.73    (KGA_MATH_BITLIST 32767)......4109 / 2.72    (_BITS 32767).................4156 / 2.69    (BITSL2 32767)...............11125 / 1    (BITSL2 32767)...............11172 / 1 <slowest>Elapsed milliseconds / relative speed for 65536 iteration(s):    (BITSJ1 128)...............1062 / 3.9 <fastest>    (BITSJ1 128)...............1078 / 3.84    (BITSMR 128)...............1328 / 3.12    (BITSMR 128)...............1328 / 3.12    (BITSL1 128)...............2968 / 1.4    (BITSL1 128)...............2984 / 1.39    (_BITS 128)................4000 / 1.04    (KGA_MATH_BITLIST 128).....4016 / 1.03    (KGA_MATH_BITLIST 128).....4031 / 1.03    (_BITS 128)................4094 / 1.01    (BITSL2 128)...............4125 / 1    (BITSL2 128)...............4141 / 1 <slowest>`
Code: [Select]
`(defun bitsMR ( n / bit bitl rtn ) ;;; n - integer ; (bits 20000) => (32 512 1024 2048 16384) ; (bits -20000) => (-16384 -2048 -1024 -512 -32) ; (bits 0) => nil  (if (minusp n)    (progn      (setq bit -0.5)      (while (>= (setq bit (fix (* bit 2.0))) n)        (setq bitl (cons bit bitl))      )      (foreach bit (reverse bitl)        (if (= (logand (- bit) (- n)) (- bit))          (setq rtn (cons bit rtn))        )      )      rtn    )    (progn      (setq bit 0.5)      (while (<= (setq bit (fix (* bit 2.0))) n)        (setq bitl (cons bit bitl))      )      (foreach bit (reverse bitl)        (if (= (logand bit n) bit)          (setq rtn (cons bit rtn))        )      )      (reverse rtn)    )  )); -- Function MeGetBitwise; Returns a list of all logical bitwise AND's of an integer.; Copyright:;   ©1998 MENZI ENGINEERING GmbH, Switzerland; Arguments [Typ]:;   Val = Value [INT]; Return [Typ]:;   > List of logical bitwise AND's [LIST]; Notes:;   None;(defun BitsJ1 (n / b o) ; > MeGetBitwise      (setq b 1)      (while (<= b n)        (if (= (logand n b) b)          (setq o (cons b o))        )        (setq b (* b 2))      )      (reverse o))(defun bitsL1 ( n / b r )    (repeat (setq b 32) (setq r (cons (logand n (lsh 1 (setq b (1- b)))) r)))    (vl-remove 0 r))(defun bitsL2 ( n )    (if (/= 0 n) (vl-remove 0 (cons (logand 1 n) (mapcar '(lambda ( x ) (lsh x 1)) (bitsL2 (lsh n -1)))))))(defun KGA_Math_BitList (int)  (vl-remove    0    (mapcar      '(lambda (idx) (lsh (lsh (lsh int (- 31 idx)) -31) idx))      '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31)    )  ))(defun _bits ( int )  (vl-remove    0    (mapcar      '(lambda ( idx ) (lsh (lsh (lsh int (- 31 idx)) -31) idx))      '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31)    )  )) (defun _int ( l1 l2 / rtn )  (foreach x l1    (if (vl-position x l2)      (setq rtn (cons x rtn))    )  )  (reverse rtn)) (defun _uni ( l1 l2 / unique )  (defun unique ( l )    (if l      (cons (car l)        (unique (vl-remove (car l) l))      )    )  )  (unique (append l1 l2))) (defun _logand ( i1 i2 )  (apply '+ (_int (_bits i1) (_bits i2)))) (defun _logior ( i1 i2 )  (apply '+ (_uni (_bits i1) (_bits i2))))`
« Last Edit: February 03, 2019, 05:15:38 AM by Marc'Antonio Alessi »

Lee Mac

• Seagull
• Posts: 12241
• London, England
Re: bits...
« Reply #7 on: February 03, 2019, 05:28:55 AM »
Apples/Oranges

Code: [Select]
`_\$ (bitsmr -512)(-512)_\$ (bitsj1 -512)nil_\$ (bitsl1 -512)(512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 -2147483648)_\$ (bitsl2 -512)(512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 -2147483648)_\$ (kga_math_bitlist -512)(512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 -2147483648)`

roy_043

• Water Moccasin
• Posts: 1703
• BricsCAD 18
Re: bits...
« Reply #8 on: February 03, 2019, 08:51:07 AM »
BricsCAD/AutoCAD?

gile

• Water Moccasin
• Posts: 2222
• Marseille, France
Re: bits...
« Reply #9 on: February 03, 2019, 09:07:33 AM »
I know (logand), (logior) functions work and for negative numbers, but I don't understand the logic behind... Any insight is welcome...

I'll try an explaination.
To make things more readable, we'll consider 8 bits signed integers, i.e. range [-128..127] (where the most significant bit (128) is used for the sign).
A negative number (let's say -100) is the 1's complement (bitwise not) of its absolute value minor one (99).
Code - Auto/Visual Lisp: [Select]
1. (~ 99) ; -> -100
The bits for 99 are:
Code: [Select]
`01100011 -> (logior 64 32 2 1)`So the bits for -100 are:
Code: [Select]
`10011100 -> (logior -128 16 8 4)`
« Last Edit: February 03, 2019, 09:11:25 AM by gile »
Speaking English as a French Frog

ribarm

• Water Moccasin
• Posts: 2108
• Marko Ribar, architect
Re: bits...
« Reply #10 on: February 04, 2019, 03:48:12 AM »
In VLIDE I got something different than your 0 and 1 bits...
Marko Ribar, d.i.a. (graduated engineer of architecture)

M.R. on Youtube

ribarm

• Water Moccasin
• Posts: 2108
• Marko Ribar, architect
Re: bits...
« Reply #11 on: February 04, 2019, 06:21:32 AM »
Using @Roy's sub :

Code: [Select]
`Command: (_bits 99)(1 2 32 64)Command: (_bits -100)(4 8 16 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 -2147483648)`
Code: [Select]
`Command: (apply 'logior (_bits 99))99Command: (apply 'logior (_bits -100))-100`
« Last Edit: February 04, 2019, 06:28:03 AM by ribarm »
Marko Ribar, d.i.a. (graduated engineer of architecture)

M.R. on Youtube

gile

• Water Moccasin
• Posts: 2222
• Marseille, France
Re: bits...
« Reply #12 on: February 04, 2019, 06:57:10 AM »
In VLIDE I got something different than your 0 and 1 bits...

Because the VLIDE uses a 'signed notation' for binary.
As LISP uses 32 bits integers, the 'classical notation' for 99 should be:
Code: [Select]
`0000 0000 0000 0000 0000 0000 0110 0011`and for -100 or (~ 99)
Code: [Select]
`1111 1111 1111 1111 1111 1111 1001 1100`And assuming the Most Significant Bit is the sign bit (2^31 = -2147483648), this matches Roy's or Lee's results.

Try this:
Code - Auto/Visual Lisp: [Select]
1. (mapcar '(lambda (e b) (* b (expt 2 e)))
2.         '(31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0)
3.         '(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1)
4. )
5.
6. (mapcar '(lambda (e b) (* b (expt 2 e)))
7.         '(31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0)
8.         '(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0)
9. )

Speaking English as a French Frog

ribarm

• Water Moccasin
• Posts: 2108
• Marko Ribar, architect
Re: bits...
« Reply #13 on: February 04, 2019, 03:32:18 PM »
In math I learned :
(2^31 = +2147483648)

In PC math :
(2^31 = -2147483648)
Marko Ribar, d.i.a. (graduated engineer of architecture)

M.R. on Youtube

Lee Mac

• Seagull
• Posts: 12241
• London, England
Re: bits...
« Reply #14 on: February 04, 2019, 03:52:19 PM »
In math I learned :
(2^31 = +2147483648)

In PC math :
(2^31 = -2147483648)

Two's complement