Shifting Challenge

Overview

Using shift in Java and some surprising edge cases.

Getting the sign

For the following program, what is the values for n so that I can change the type of x without having to change the code. 
// sign is 1 if negative and 0 if non-negative
long sign = x >>> n;
There is a value you can replace n such that you don't need to know the type of x

Similarly, I want to shift the lowest bit to be the highest without knowing what type I am shifting 

// sign is MIN_VALUE if odd otherwise 0
long sign = x << n;

For bonus points, write formula for all the possible solutions of n (there is more than one)

Is a power of two

How do you determine an integer is a power of 2.

This is a fairly common interview question. Its pretty hard to figure out in an interview I imagine. To save you googling, you can write this in C with 

x&&!(x&(x-1))
In Java, you can write this using just 0 ~ - & == != . Complete this expression using those operators 
long x = 
boolean isPow2 = x != 0 .....

Comments

  1. Fahd Shariff19 January 2012 at 09:21

    boolean isPow2 = (x != 0) && (x & (x - 1)) == 0;

    ReplyDelete
  2. Peter Lawrey19 January 2012 at 09:27

    Ok, so now do it without && and where the only number is 0. Hint, you can use ~

    ReplyDelete
  3. Yury Vasyutinskiy22 January 2012 at 10:23

    Getting sign
    1. n = 63, works good, cause all type sizes are the power of two. So when >>> operator is used we can simply put the biggest size and in case of smaller types circular shifts are done.
    2. n = -1, this works for all types, but there's slight different results for long and other types. For long it would yield Long.MIN_VALUE and for others Integer.MIN_VALUE if odd.

    Is a power of two
    Just change C expression with provided operators:
    boolean isPow2 = (x != 0) & ((x & (x - ((~0)>>>31)))) == 0)

    ReplyDelete
  4. Peter Lawrey22 January 2012 at 10:29

    A hint: How do you get 1 from 0 using only - and ~

    ReplyDelete
    Replies
    1. Yury Vasyutinskiy22 January 2012 at 17:57

      Yes, this is much simpler and more clear, thank's.
      The updated expression is:
      boolean isPow2 = (x != 0) & ((x & (x - (-(~0)))) == 0);

      Delete
    2. Peter Lawrey22 January 2012 at 18:07

      See if you can remove some of the ( ) ;)

      Delete
  5. Peter Lawrey22 January 2012 at 10:30

    Shifting by 63 and -1 is identical. Shifting by N << 6 + M always shifts by M. For int values its N << 5 + M.

    ReplyDelete

Post a Comment

Popular posts from this blog

Why You Should Tune Code Before Your Garbage Collector

Image
Optimising your memory allocations in Java could make far more difference than your choice of Garbage Collector and may even change which is the best garbage collector. In this post I look at a simple event to response latency benchmark, MarketDataSnapshot to NewOrderSingle at 50K/s for 30 minutes using JLBH to test Chronicle-FIX. The goal is to compare a system which is doing redundant work (in this case logging each message using SLF4J), compared with not logging (Chronicle-FIX records every message internally using Chronicle Queue) and how this changes the choice of Garbage Collector For the p99 (worst 1 in 100) the choice of Garbage Collector makes a different on par with optimising how loggin is done However, for the p99.99 (worst 1 in 10,000) optimsing how the logging is done is orders of magnitude more signifciant than the choice of Garbage Collector Unoptimised Benchmark This takes the optimised benchmark and adds one SLF4J log line of just ...
Read more

Asking multiple AI to optimise the same code

As different AIs are implemented differently, they don't all provide the same answer, nor do they consistently outperform one another. The best approach is to use multiple AI and pick the one you like best. My goal here is not to declare a winner based on one example, but instead to show the variety of answers you can get with different AI. I asked each AI to Suggest how to implement this more optimally private static String formatOffset(int millis) { String sign = millis < 0 ? "-" : "+"; int saveSecs = Math.abs(millis) / 1000; int hours = saveSecs / 3600; int mins = ((saveSecs / 60) % 60); int secs = (saveSecs % 60); if (secs == 0) { if (mins == 0) { return sign + twoDigitString(hours); } return sign + twoDigitString(hours) + twoDigitString(mins); } return sign + twoDigitString(hours) + twoDigitString(mins) + twoDigitString(secs); } private static String twoDigitString(int value) { ...
Read more

Which Doc Format is Best for AI Specifications?

I have a Spec Driven Project with 674 documents incl 181 specs, 429 tasks, and 40 project docs. About 1/3 of these are an acceptance sub-project to show the root project meets fit-for-purpose requirements. I used Fable to convert these to and from AsciiDoc, Markdown, and HTML. From this, I tried to draw some conclusions about which format is better than the others for AI specifications. TL;DR: Markdown for AI working documents, AsciiDoc for curated human-reviewed specs, HTML only as a publishing target. Objective Metrics Corpus Tokens (Approx) Markdown: 594k, AsciiDoc: 598K, HTML: 661k Worst Single-File Ratio AsciiDoc: 1.023x, HTML: 1.26x (due to tables and code blocks) Markup share of file content Markdown 0.9%, AsciiDoc 1.3%, HTML 9.9% - a 10x overhead for HTML Read/write Assessment In terms of readability, both Markdown and AsciiDoc are good. HTML has far more tags, which add noise. One of the most common tags is <code> some code </c...
Read more