home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / arch / 8866 < prev    next >
Encoding:
Internet Message Format  |  1992-08-12  |  2.6 KB
  1. Path: sparky!uunet!decwrl!infopiz!lupine!jcb
  2. Newsgroups: comp.arch
  3. Subject: Re: Finding which bit set in a bit-string.
  4. Message-ID: <9208121953.AA05683@verbosa.ncd.com>
  5. From: jcb (Jim Becker)
  6. Date: 12 Aug 92 19:53:58 GMT
  7. Sender: news@NCD.COM
  8. References: <9208041713.AA16446@verbosa.ncd.com><1992Aug6.153710.8565@crd.ge.com><1992Aug6.175602.19433@bcars64a.bnr.ca>
  9. Nntp-Posting-Host: verbosa
  10. Return-Path: <jcb>
  11. To: postnews
  12. Lines: 51
  13.  
  14.  
  15.    From: schow@bqneh3.bnr.ca (Stanley T.H. Chow)
  16.    
  17.    In article <1992Aug6.153710.8565@crd.ge.com> davidsen@crd.ge.com (bill davidsen) writes:
  18.    >In article <9208041713.AA16446@verbosa.ncd.com>, jcb (Jim Becker) writes:
  19.    >
  20.    >| next  question -- how do you create a bi-directional linked list using
  21.    >| a single 32 bit pointer??? gee, another "trick"!! :)
  22.    >
  23.    >  Pretty neat trick if you have an answer. Or is this a trick question
  24.    >where you say "I didn't tell you that the range of the values is
  25.    >constrained?" Please post to comp.compression, too, how you represent
  26.    >any two possible 32 bit values in only 32 bits.
  27.    
  28.    The question is mis-phrased. The problem is really:
  29.    
  30.       How do you bi-directionally traverse a singly linked list without
  31.       needing extra storage.
  32.    
  33. this is a fuzzy problem definition  as  well,  but  i  really  am  not
  34. interested  in  getting into semantics arguments. please excuse me for
  35. not  being  more  verbose  in  the  problem  description  (very out of
  36. character for me, i can assure you.. :).)
  37.  
  38. my idea was to get across  the  concept  of  people  asking  interview
  39. questions  that  are  "meaningless  tricks"  rather  than  those which
  40. discern problem solving techniques and experience.
  41.  
  42.    There are many capabilities of true double links that are not possible
  43.    with the xor scheme.
  44.  
  45.    Stanley Chow            InterNet: schow@BNR.CA
  46.  
  47. i always use double links, and have never used tricks like  this,  for
  48. bi-directional list traversal. however, those who mention you can only
  49. traverse the list from first<->last don't  think  of  retaining  _two_
  50. pointers  into  the  list.  with _two_ pointers you can do the same as
  51. with  _one_  in  a "true" bi-directional list, albeit with XOR hacking
  52. and more pointer management overhead.
  53.  
  54. like i said, i don't code like this. but it might  be  useful  if  you
  55. have memory restraints and like people to call you  "King  Hacker"  to
  56. your face.. :)
  57.  
  58. apologies  to  those  who  don't  feel  this is appropriate use of the
  59. comp.arch newgroup.  so how many mflops come enabled with  a  base  P5
  60. anyway? :*)
  61.  
  62. -jim
  63. --
  64.  -Jim Becker / jcb@ncd.com   /   Network Computing Devices, Inc. (NCD)
  65.