I am out of ideas to solve it

Question about the task

Let's find the highest power of 2

Java Multithreading, Level 10, Lesson 8

Under discussion

How to solve without declaring any variable or without using any operators

Implement the maxPowerOf2 method, which should return the highest power of 2 that fits into the passed number.
The maxPowerOf2 argument can only be a positive integer.

Use only the following operations:
1) Bitwise shifts.
2) Bitwise OR.
3) Bitwise AND.
4) Bitwise unary NOT.
5) Assignment (you can combine the allowed operations with assignment, e.g. &=).
6) Curly braces.
Don't leave any comments.
Don't declare any variables. Only use x, which is passed as an argument to the maxPowerOf2 method.
The main method is not tested.

Requirements:

The Solution class must have a maxPowerOf2(int) method.
In the Solution class's maxPowerOf2(int) method, use only the allowed operations.
In the Solution class's maxPowerOf2(int) method, don't use operations that aren't allowed.
Implement the maxPowerOf2(int) method, which should return the highest power of 2 that fits into the passed number.

package com.codegym.task.task30.task3007; /* Let's find the highest power of 2 */ public class Solution { public static void main(String[] args) { System.out.println(maxPowerOf2(140_000)); // 131072 System.out.println(maxPowerOf2(1026)); // 1024 System.out.println(maxPowerOf2(17)); // 16 } public static int maxPowerOf2(int x) { int m = 1; x |= x>>1; x |= x>>2; x |= x>>4; x |= x>>8; x |= x>>16; while ((int)(x & m) >= 1){ x = x^m; m <<= 1; } x = x^m; return (x>>1); } }

Comments (6)

Popular
New
Old

You must be signed in to leave a comment

Kubańczyk92 QA Automation Engineer

6 December 2022, 10:43

If you have issues with understanding the solution given by our colleagues below here is the way how to calculate bitwaise or:

and here is how the biwaise xor is calculated (^ at the end of the method in the return statement):

by following the code below(will be pasted in two chunks because it is too long to add it as one comment) you can see, step by step how the values are transformed:

Kubańczyk92 QA Automation Engineer

6 December 2022, 10:44

package com.codegym.task.task30.task3007;
public class Solution {
    public static void main(String[] args) {
        System.out.println(maxPowerOf2(140_000));   // 131072
    }

    public static int maxPowerOf2(int x) {
        System.out.println(x + " " + Integer.toBinaryString(x));
        System.out.println(Integer.parseInt(Integer.toBinaryString(x >> 1), 2) + "   " + Integer.toBinaryString(x >> 1));
        x |= x >> 1;
        System.out.println("--------------------------");
        System.out.println(x + " " + Integer.toBinaryString(x));
        System.out.println();


        System.out.println(x + " " + Integer.toBinaryString(x));
        System.out.println(Integer.parseInt(Integer.toBinaryString(x >> 2), 2) + "    " + Integer.toBinaryString(x >> 2));
        x |= x >> 2;
        System.out.println("--------------------------");
        System.out.println(x + " " + Integer.toBinaryString(x));
        System.out.println();


        System.out.println(x + " " + Integer.toBinaryString(x));
        System.out.println(Integer.parseInt(Integer.toBinaryString(x >> 4), 2) + "      " + Integer.toBinaryString(x >> 4));
        x |= x >> 4;
        System.out.println("--------------------------");
        System.out.println(x + " " + Integer.toBinaryString(x));
        System.out.println();
////END OF PART1

Kubańczyk92 QA Automation Engineer

6 December 2022, 10:44

System.out.println(x + " " + Integer.toBinaryString(x));
        System.out.println(Integer.parseInt(Integer.toBinaryString(x >> 8), 2) + "           " + Integer.toBinaryString(x >> 8));
        x |= x >> 8;
        System.out.println("--------------------------");
        System.out.println(x + " " + Integer.toBinaryString(x));
        System.out.println();


        System.out.println(x + " " + Integer.toBinaryString(x));
        System.out.println(Integer.parseInt(Integer.toBinaryString(x >> 16), 2) + "                      " + Integer.toBinaryString(x >> 16));
        x |= x >> 16;
        System.out.println("--------------------------");
        System.out.println(x + " " + Integer.toBinaryString(x));
        System.out.println();

        System.out.println("Moving the number : " + x + " " + "by using  x >> 1 gives: " + Integer.parseInt(Integer.toBinaryString(x >> 1), 2));
        System.out.println(Integer.parseInt(Integer.toBinaryString(x >> 1), 2) + "  0" + Integer.toBinaryString(x >> 1));
        System.out.println();
        System.out.println("expression: x ^ (x >> 1) is equal to 262143 ^ 131071 which the binary representation is:");
        System.out.println(x + " " + Integer.toBinaryString(x));
        System.out.println(Integer.parseInt(Integer.toBinaryString(x >> 1), 2) + " 0" + Integer.toBinaryString(x >> 1));
        System.out.println("--------------------------");
        System.out.println(Integer.parseInt(Integer.toBinaryString(x ^ (x >> 1)), 2) + " " + Integer.toBinaryString(x ^ (x >> 1)));

        return x ^ (x >> 1);
    }
}

Anonymous #10436715

Level 38

25 May 2020, 19:02

This works too:

public static int maxPowerOf2(int x) {
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    return x ^ (x >> 1);
}

Wei Cui

Level 39 , Newark, United States

13 April 2020, 16:44

public static int maxPowerOf2(int x) {
        x |= x >> 1;
        x |= x >> 2;
        x |= x >> 4;
        x |= x >> 8;
        x |= x >> 8;
        x |= x >> 8;

        return x ^ (x >> 1);
    }

Mateusz

Level 36 , Wroclaw, Poland

11 March 2020, 09:15

Close, That small tip for you: Instead of use loop and additional variable. you should use : Bitwise AND, NOT, and shifts