From owner-freebsd-hackers@FreeBSD.ORG Sun Jun 7 00:13:27 2015 Return-Path: Delivered-To: freebsd-hackers@FreeBSD.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id C482FE9A for ; Sun, 7 Jun 2015 00:13:27 +0000 (UTC) (envelope-from erichsfreebsdlist@alogt.com) Received: from alogt.com (alogt.com [69.36.191.58]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 994231664 for ; Sun, 7 Jun 2015 00:13:27 +0000 (UTC) (envelope-from erichsfreebsdlist@alogt.com) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=alogt.com; s=default; h=Content-Transfer-Encoding:Content-Type:MIME-Version:Message-ID:Subject:To:From:Date; bh=7ngDWCIl/+mt/Iyfh/HI9qCWkYzc54Kpyf9orfxgBHY=; b=XJk0uJLA13/DZrS2DyoCHCcNm/ISYYn99v/Yfv3BTAcyh4VZps7SGc5rbJ4MblJ158oQk/chfUYsZ5+XU75UcFv/uTnpxkj6iy9o7hUXVAW/We7GeUjAqDcLASXZw683sBTVNWOxLUjK9ptRgy+pjWfz+dcyZ1OeMkcbAm2lCCE=; Received: from [114.124.31.137] (port=57424 helo=B85M-HD3-0.alogt.com) by sl-508-2.slc.westdc.net with esmtpsa (TLSv1.2:AES128-GCM-SHA256:128) (Exim 4.85) (envelope-from ) id 1Z1ODH-003xrN-TR for freebsd-hackers@FreeBSD.org; Sat, 06 Jun 2015 18:13:20 -0600 Date: Sun, 7 Jun 2015 08:13:15 +0800 From: Erich Dollansky To: "freebsd-hackers@freebsd.org" Subject: allow ffs & co. a binary search Message-ID: <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - sl-508-2.slc.westdc.net X-AntiAbuse: Original Domain - freebsd.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - alogt.com X-Get-Message-Sender-Via: sl-508-2.slc.westdc.net: authenticated_id: erichsfreebsdlist@alogt.com X-Source: X-Source-Args: X-Source-Dir: X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 07 Jun 2015 00:13:27 -0000 Hi, I stumbled these days over the functions to find the first or last bit set. They are currently written like this: /* * Find First Set bit */ int ffs(int mask) { int bit; if (mask == 0) return (0); for (bit = 1; !(mask & 1); bit++) mask = (unsigned int)mask >> 1; return (bit); } With other words, the program loops until it finds what it searches for. Why not do it the binary way? int res; res = 0; IF (Number != 0) THEN res = 1; IF ((Number & 0xFFFFFFFF00000000) != 0) THEN Number = Number & 0xFFFFFFFF00000000; res = res + 32; END; IF ((Number & 0xFFFF0000FFFF0000) != 0) THEN Number = Number & 0xFFFF0000FFFF0000; res = res + 16; END; IF ((Number & 0xFF00FF00FF00FF00) != 0) THEN Number = Number & 0xFF00FF00FF00FF00; res = res + 8; END; IF ((Number & 0xF0F0F0F0F0F0F0F0) != 0) THEN Number = Number & 0xF0F0F0F0F0F0F0F0; res = res + 4; END; IF ((Number & 0xCCCCCCCCCCCCCCCC) != 0) THEN Number = Number & 0xCCCCCCCCCCCCCCCC; res = res + 2; END; IF ((Number & 0xAAAAAAAAAAAAAAAA) != 0) THEN Number = Number & 0xAAAAAAAAAAAAAAAA; res = res + 1; END; END; return res; If you like the binary way I could give you the sources for the complete family following your style to replace the older functions. Erich