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

0 Members and 1 Guest are viewing this topic.

ribarm

  • Water Moccasin
  • Posts: 2069
  • 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: 1677
  • 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.    (mapcar
  4.      '(lambda (idx) (lsh (lsh (lsh int (- 31 idx)) -31) idx))
  5.      '(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)
  6.    )
  7.  )
  8. )
(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: 985
  • 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: 2069
  • 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.    (mapcar
  4.      '(lambda ( idx ) (lsh (lsh (lsh int (- 31 idx)) -31) idx))
  5.      '(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)
  6.    )
  7.  )
  8. )
  9.  
  10. (defun _int ( l1 l2 / rtn )
  11.  (foreach x l1
  12.    (if (vl-position x l2)
  13.      (setq rtn (cons x rtn))
  14.    )
  15.  )
  16.  (reverse rtn)
  17. )
  18.  
  19. (defun _uni ( l1 l2 / unique )
  20.  (defun unique ( l )
  21.    (if l
  22.      (cons (car l)
  23.        (unique (vl-remove (car l) l))
  24.      )
  25.    )
  26.  )
  27.  (unique (append l1 l2))
  28. )
  29.  
  30. (defun _logand ( i1 i2 )
  31.  (apply '+ (_int (_bits i1) (_bits i2)))
  32. )
  33.  
  34. (defun _logior ( i1 i2 )
  35.  (apply '+ (_uni (_bits i1) (_bits i2)))
  36. )
  37.  

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: 1677
  • 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: 12195
  • 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: 985
  • 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 Reserved
Elapsed 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: 12195
  • 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: 1677
  • BricsCAD 18
Re: bits...
« Reply #8 on: February 03, 2019, 08:51:07 AM »
BricsCAD/AutoCAD?

gile

  • Water Moccasin
  • Posts: 2204
  • 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: 2069
  • 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: 2069
  • 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))
99
Command: (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: 2204
  • 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 0011and for -100 or (~ 99)
Code: [Select]
1111 1111 1111 1111 1111 1111 1001 1100And 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: 2069
  • 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: 12195
  • 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