From owner-freebsd-hackers Sat Aug 21 12:10:24 1999 Delivered-To: freebsd-hackers@freebsd.org Received: from donhm.calcasieu.com (tcnet05-62.austin.texas.net [209.99.42.62]) by hub.freebsd.org (Postfix) with ESMTP id 253E21546D for ; Sat, 21 Aug 1999 12:10:12 -0700 (PDT) (envelope-from dread@texas.net) Received: from donhm.calcasieu.com (localhost.calcasieu.com [127.0.0.1]) by donhm.calcasieu.com (8.8.8/8.8.8) with ESMTP id OAA28671; Sat, 21 Aug 1999 14:11:03 -0500 (CDT) (envelope-from dread@texas.net) Message-ID: X-Mailer: XFMail 1.3 [p0] on FreeBSD X-Priority: 3 (Normal) Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 8bit MIME-Version: 1.0 In-Reply-To: Date: Sat, 21 Aug 1999 14:11:03 -0500 (CDT) From: Don Read To: Nick Hibma Subject: RE: from number to power of two Cc: FreeBSD Hackers mailing list Sender: owner-freebsd-hackers@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG On 21-Aug-99 Nick Hibma wrote: > > Does anyone know an inexpensive algorithm (O(1)) to go from an number to > the next (lower or higher) power of two. > > 1 -> 1 > 2,3 -> 2 > 4,5,6,7 -> 4 > 8,9,10,11,12,13,14,15 -> 8 > etc. > > So %1101 should become either %10000 or %1000. > > The only solution I have so far is a table. That is a possibility as the > the highest number will be 32 I think. a bit of fiddling around gives: int pw2(register unsigned i) { register unsigned cnt=1; do { i >>= 1; cnt <<=1; /* printf("[%x %x],",i, cnt); */ } while (i); /* return(cnt) /* higher */ return( cnt >> 1); /* in bound */ /* return(cnt >> 2); /* lower */ } Prolly should do boundry check for case 0 : 0 -> 0 ? 0 -> 1. Regards, --- Don Read dread@calcasieu.com EDP Manager dread@texas.net Calcasieu Lumber Co. Austin TX -- But I'm in good company, sendmail has kicked a great many butts in the past To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message