Determine the number of bits in a negative number
in [VbScript]
|
From: Csaba Gabor on 2 Dec 2009 19:17 On Dec 2, 6:46 pm, mr_unreliable <kindlyReplyToNewsgr...(a)notmail.com> wrote: > Csaba Gabor wrote: > > I'd like to determine the number of bits (the position > > of the highest on bit) in a negative number (say -1) > > without using knowledge of its type. > > The "brute force" way would be to "shift left" one bit > at a time, until you hit your 1-bit. > > Problem is, you can't shift left in script. There are > a number of shifting functions written in VB, but they > require calling the system api. You can shift left in VBScript - Just multiply the number by 2. The problem is that if you have 2^14 (as an integer) and you shift left by 1 it becomes a long so that the sign does not go negative. And while this isn't a problem with positive numbers, it is a problem with the negatives, since the sign keeps getting extended. In other words, as you keep multiplying your bit selector by 2, it will eventually turn from an integer to a long. When you and or xor it with the number being tested, that in turn will turn into the type matching the selector, extending any leading 1s for negative numbers. Nevertheless, this is the approach that I've used. The highest bit position for a negative number is given by the highest bit position for a -1, which can be trivially givien if one presumes to know how many bytes it takes to represent a given type. But that's what I didn't want to tie myself to. > Most scripters abhor calling the system api, and so > your best bet is to wait around for a more knowledgable > person to come along with a "pure script" solution. > > cheers, jw
From: Csaba Gabor on 2 Dec 2009 19:42 On Dec 2, 7:27 pm, Tom Lavedas <tlave...(a)gmail.com> wrote: > On Dec 2, 12:46 pm, mr_unreliable <kindlyReplyToNewsgr...(a)notmail.com> > wrote: > > > Csaba Gabor wrote: > > > I'd like to determine the number of bits (the position > > > of the highest on bit) in a negative number (say -1) > > > without using knowledge of its type. > > > The "brute force" way would be to "shift left" one bit > > at a time, until you hit your 1-bit. > > > Problem is, you can't shift left in script. There are > > a number of shifting functions written in VB, but they > > require calling the system api. > > > Most scripters abhor calling the system api, and so > > your best bet is to wait around for a more knowledgable > > person to come along with a "pure script" solution. > > > cheers, jw > > JScript has SHIFT operators, so the old trick of using JScript in VBS > will work ... > > wsh.echo ShiftRight(clng(-1) and &h7fffffff&, 30) > > Function ShiftRight(arg, n) > with createobject("htmlfile") > .write "<script>var a=" & arg & ">>" & n & ";</script>" > ShiftRight = .parentWindow.a > end with > end function > > Function ShiftLeft(arg, n) > with createobject("htmlfile") > .write "<script>var a=" & arg & "<<" & n & ";</script>" > ShiftLeft = .parentWindow.a > end with > end function Hi Tom, VBScript can do JS style of shifting just fine, I think: For shift left, just multiply by 2 (or add the number to itself), which should work for both positive and negative integers. For shift right, the situation is a bit more complicated. It amounts to a floor operation after division by a power of 2: x >> n is: x AND (-1 XOR 2^n-1) / 2^2 Though the type of notation I've used may cause the type of the result to change (since 2^n produces a double, for example). > I also propose ANDing the number (converted to a Long - 32 bit - > number) with a mask that zeros the minus sign bit. Then the other This is what I'm trying to avoid. You have presumed to know where the high bit is already (in the case of negative numbers). > bits can be tested. The shift that first returns a value of zero is > the most significant bit (I didn't bother to show the test loop). > BTW, your shift nomenclature seems backward to me. I guess you were > thinking of shifting the mask and not the number. However, starting > from the MSB end would still seem most efficient and would still shift > the mask to the right, not the left wouldn't it? Your conclusion is only valid if you presume you know where the high bit must be (in which case you will get a trivial answer for negative numbers, but no clear win for positive numbers). However, the bit shifting approach from right to left must have a basis for termination, which is the hard part, I think.
From: Csaba Gabor on 2 Dec 2009 20:19
On Dec 2, 11:17 pm, "Paul Randall" <paulr...(a)cableone.net> wrote: > "mr_unreliable" <kindlyReplyToNewsgr...(a)notmail.com> wrote in message > > news:u1ybAb3cKHA.5156(a)TK2MSFTNGP04.phx.gbl... > > > > > > > Csaba Gabor wrote: > >> I'd like to determine the number of bits (the position > >> of the highest on bit) in a negative number (say -1) > >> without using knowledge of its type. > > > The "brute force" way would be to "shift left" one bit > > at a time, until you hit your 1-bit. > > > Problem is, you can't shift left in script. There are > > a number of shifting functions written in VB, but they > > require calling the system api. > > > Most scripters abhor calling the system api, and so > > your best bet is to wait around for a more knowledgable > > person to come along with a "pure script" solution. > > If the task must be done without using "knowledge of its type", then double > precision floats might be involved, which could be a lot of bits that don't > shift nicely Only integers (but not integer types are presumed). When I posed the question, I didn't have a solution - this problem has been bugging me since around the time of http://groups.google.com/group/microsoft.public.vb.general.discussion/browse_frm/thread/1732616a8f0a7d02 But I realized that I had made the conditions a bit too harsh, and really meant that one shouldn't presume knowledge of any specific type (as opposed to knowing its type). So I programmed up a solution based on detecting a type change. Still, I was not happy with this, so in writing this up I have produced the following which has worked for all my test cases, and about which I am less unhappy (improvements welcome): MsgBox HighBitPos (0) '-1 MsgBox HighBitPos(27) '4 MsgBox HighBitPos(16384) '14 MsgBox HighBitPos(2^14) '14 MsgBox HighBitPos(32768) '15 MsgBox HighBitPos(2^15) '15 MsgBox HighBitPos(-1) '15 MsgBox HighBitPos (-&1&) '15 MsgBox HighBitPos(&H10FFFF) '20 MsgBox HighBitPos(-&HFFFF&) '31 Function HighBitPos(n) HighBitPos = -1 On Error Resume Next Dim bit, typ: bit=1: typ=typename(n) While typ=typename(n) AND n<>0 HighBitPos = HighBitPos + 1 If (n AND bit) Then n = n XOR bit If n = -n OR bit=-n Then exit Function bit = 2*bit Wend ' HighBitPos = HighBitPos & " " & typ End Function Csaba Gabor from Vienna That on error is there because of the last case. When missing, it will die on the first If. |