Dado un número entero n > 0, la tarea es encontrar si en el patrón de bits del recuento de números enteros los 1 continuos aumentan de izquierda a derecha.
Ejemplos:
Input:19 Output:Yes Explanation: Bit-pattern of 19 = 10011, Counts of continuous 1's from left to right are 1, 2 which are in increasing order. Input : 183 Output : yes Explanation: Bit-pattern of 183 = 10110111, Counts of continuous 1's from left to right are 1, 2, 3 which are in increasing order.
Una solución simple es almacenar la representación binaria de un número dado en una string, luego recorrer de izquierda a derecha y contar el número de 1 continuos. Para cada encuentro de 0, verifique el valor del conteo anterior de 1 continuos al valor actual, si el valor del conteo anterior es mayor que el valor del conteo actual, devuelva Falso, de lo contrario, cuando finalice la string, devuelva Verdadero.
C++
// C++ program to find if bit-pattern
// of a number has increasing value of
// continuous-1 or not.
#include <bits/stdc++.h>
using namespace std;
// Returns true if n has increasing count of
// continuous-1 else false
bool findContinuous1(int n)
{
const int bits = 8 * sizeof(int);
// store the bit-pattern of n into
// bit bitset- bp
string bp = bitset<bits>(n).to_string();
// set prev_count = 0 and curr_count = 0.
int prev_count = 0, curr_count = 0;
int i = 0;
while (i < bits) {
if (bp[i] == '1') {
// increment current count of continuous-1
curr_count++;
i++;
}
// traverse all continuous-0
else if (bp[i - 1] == '0') {
i++;
curr_count = 0;
continue;
}
// check prev_count and curr_count
// on encounter of first zero after
// continuous-1s
else {
if (curr_count < prev_count)
return 0;
i++;
prev_count = curr_count;
curr_count = 0;
}
}
// check for last sequence of continuous-1
if (prev_count > curr_count && (curr_count != 0))
return 0;
return 1;
}
// Driver code
int main()
{
int n = 179;
if (findContinuous1(n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program to find if bit-pattern
// of a number has increasing value of
// continuous-1 or not.
import java.io.*;
public class GFG {
// Returns true if n has increasing count of
// continuous-1 else false
static boolean findContinuous1(int n)
{
// converting decimal integer to binary string then
// store the bit-pattern of n into
// bit bitset- bp by converting the binary string to
// char array
char[] bp
= (Integer.toBinaryString(n)).toCharArray();
int bits = bp.length;
// set prev_count = 0 and curr_count = 0.
int prev_count = 0;
int curr_count = 0;
int i = 0;
while (i < bits) {
if (bp[i] == '1')
{
// increment current count of continuous-1
curr_count++;
i++;
}
// traverse all continuous-0
else if (bp[i - 1] == '0') {
i++;
curr_count = 0;
continue;
}
// check prev_count and curr_count
// on encounter of first zero after
// continuous-1s
else {
if (curr_count < prev_count)
return false;
i++;
prev_count = curr_count;
curr_count = 0;
}
}
// check for last sequence of continuous-1
if ((prev_count > curr_count) && (curr_count != 0))
return false;
return true;
}
// Driver code
public static void main(String args[])
{
int n = 179;
if (findContinuous1(n))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by phasing17
Python3
# Python3 program to find if bit-pattern
# of a number has increasing value of
# continuous-1 or not.
# Returns true if n has increasing count of
# continuous-1 else false
def findContinuous1(n):
# store the bit-pattern of n into
# bit bitset- bp
bp = list(bin(n))
bits = len(bp)
# set prev_count = 0 and curr_count = 0.
prev_count = 0
curr_count = 0
i = 0
while (i < bits):
if (bp[i] == '1'):
# increment current count of continuous-1
curr_count += 1
i += 1
# traverse all continuous-0
elif (bp[i - 1] == '0'):
i += 1
curr_count = 0
continue
# check prev_count and curr_count
# on encounter of first zero after
# continuous-1s
else:
if (curr_count < prev_count):
return 0
i += 1
prev_count = curr_count
curr_count = 0
# check for last sequence of continuous-1
if (prev_count > curr_count and (curr_count != 0)):
return 0
return 1
# Driver code
n = 179
if (findContinuous1(n)):
print("Yes")
else:
print("No")
# This code is contributed by SHUBHAMSINGH10
C#
// C# program to find if bit-pattern
// of a number has increasing value of
// continuous-1 or not.
using System;
using System.Collections.Specialized;
class GFG
{
// Returns true if n has increasing count of
// continuous-1 else false
static bool findContinuous1(int n)
{
// store the bit-pattern of n into
// bit bitset- bp
string bp = Convert.ToString(n, 2);
int bits = bp.Length;
// set prev_count = 0 and curr_count = 0.
int prev_count = 0, curr_count = 0;
int i = 0;
while (i < bits)
{
if (bp[i] == '1')
{
// increment current count of continuous-1
curr_count++;
i++;
}
// traverse all continuous-0
else if (bp[i - 1] == '0') {
i++;
curr_count = 0;
continue;
}
// check prev_count and curr_count
// on encounter of first zero after
// continuous-1s
else {
if (curr_count < prev_count)
return false;
i++;
prev_count = curr_count;
curr_count = 0;
}
}
// check for last sequence of continuous-1
if (prev_count > curr_count && (curr_count != 0))
return false;
return true;
}
// Driver Code
static void Main()
{
int n = 179;
if (findContinuous1(n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This Code was contributed by phasing17
Javascript
<script>
// JavaScript program to find if bit-pattern
// of a number has increasing value of
// continuous-1 or not.
function dec2bin(dec) {
return (dec >>> 0).toString(2);
}
// Returns true if n has increasing count of
// continuous-1 else false
function findContinuous1(n){
// store the bit-pattern of n into
// bit bitset- bp
let bp = dec2bin(n)
let bits = bp.length
// set prev_count = 0 and curr_count = 0.
let prev_count = 0
let curr_count = 0
let i = 0
while (i < bits){
if (bp[i] == '1'){
// increment current count of continuous-1
curr_count += 1;
i += 1;
}
// traverse all continuous-0
else if (bp[i - 1] == '0'){
i += 1
curr_count = 0
continue
}
// check prev_count and curr_count
// on encounter of first zero after
// continuous-1s
else{
if (curr_count < prev_count)
return 0
i += 1
prev_count = curr_count
curr_count = 0
}
}
// check for last sequence of continuous-1
if (prev_count > curr_count && (curr_count != 0))
return 0
return 1
}
// Driver code
n = 179
if (findContinuous1(n))
document.write( "Yes")
else
document.write( "No")
</script>
Producción :
Yes
Complejidad de tiempo: O (logn)
Espacio auxiliar: O (logn)
Una solución eficiente es usar un ciclo de conversión de decimal a binario que divide el número por 2 y toma el resto como un bit. Este bucle encuentra bits de derecha a izquierda. Entonces verificamos si de derecha a izquierda está en orden decreciente o no.
A continuación se muestra la implementación.
C++
// C++ program to check if counts of consecutive
// 1s are increasing order.
#include<bits/stdc++.h>
using namespace std;
// Returns true if n has counts of consecutive
// 1's are increasing order.
bool areSetBitsIncreasing(int n)
{
// Initialize previous count
int prev_count = INT_MAX;
// We traverse bits from right to left
// and check if counts are decreasing
// order.
while (n > 0)
{
// Ignore 0s until we reach a set bit.
while (n > 0 && n % 2 == 0)
n = n/2;
// Count current set bits
int curr_count = 1;
while (n > 0 && n % 2 == 1)
{
n = n/2;
curr_count++;
}
// Compare current with previous and
// update previous.
if (curr_count >= prev_count)
return false;
prev_count = curr_count;
}
return true;
}
// Driver code
int main()
{
int n = 10;
if (areSetBitsIncreasing(n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program to check if counts of
// consecutive 1s are increasing order.
import java .io.*;
class GFG {
// Returns true if n has counts of
// consecutive 1's are increasing
// order.
static boolean areSetBitsIncreasing(int n)
{
// Initialize previous count
int prev_count = Integer.MAX_VALUE;
// We traverse bits from right to
// left and check if counts are
// decreasing order.
while (n > 0)
{
// Ignore 0s until we reach
// a set bit.
while (n > 0 && n % 2 == 0)
n = n/2;
// Count current set bits
int curr_count = 1;
while (n > 0 && n % 2 == 1)
{
n = n/2;
curr_count++;
}
// Compare current with previous
// and update previous.
if (curr_count >= prev_count)
return false;
prev_count = curr_count;
}
return true;
}
// Driver code
static public void main (String[] args)
{
int n = 10;
if (areSetBitsIncreasing(n))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by anuj_67.
Python3
# Python3 program to check if counts of
# consecutive 1s are increasing order.
import sys
# Returns true if n has counts of
# consecutive 1's are increasing order.
def areSetBitsIncreasing(n):
# Initialize previous count
prev_count = sys.maxsize
# We traverse bits from right to
# left and check if counts are
# decreasing order.
while (n > 0):
# Ignore 0s until we reach a
# set bit.
while (n > 0 and n % 2 == 0):
n = int(n/2)
# Count current set bits
curr_count = 1
while (n > 0 and n % 2 == 1):
n = n/2
curr_count += 1
# Compare current with previous
# and update previous.
if (curr_count >= prev_count):
return False
prev_count = curr_count
return True
# Driver code
n = 10
if (areSetBitsIncreasing(n)):
print("Yes")
else:
print("No")
# This code is contributed by Smitha
C#
// C# program to check if counts of
// consecutive 1s are increasing order.
using System;
class GFG {
// Returns true if n has counts of
// consecutive 1's are increasing
// order.
static bool areSetBitsIncreasing(int n)
{
// Initialize previous count
int prev_count = int.MaxValue;
// We traverse bits from right to
// left and check if counts are
// decreasing order.
while (n > 0)
{
// Ignore 0s until we reach
// a set bit.
while (n > 0 && n % 2 == 0)
n = n/2;
// Count current set bits
int curr_count = 1;
while (n > 0 && n % 2 == 1)
{
n = n/2;
curr_count++;
}
// Compare current with previous
// and update previous.
if (curr_count >= prev_count)
return false;
prev_count = curr_count;
}
return true;
}
// Driver code
static public void Main ()
{
int n = 10;
if (areSetBitsIncreasing(n))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to check if
// counts of consecutive
// 1s are increasing order.
// Returns true if n has
// counts of consecutive
// 1's are increasing order.
function areSetBitsIncreasing( $n)
{
// Initialize previous count
$prev_count = PHP_INT_MAX;
// We traverse bits from right
// to left and check if counts
// are decreasing order.
while ($n > 0)
{
// Ignore 0s until we
// reach a set bit.
while ($n > 0 && $n % 2 == 0)
$n = $n / 2;
// Count current set bits
$curr_count = 1;
while ($n > 0 and $n % 2 == 1)
{
$n = $n / 2;
$curr_count++;
}
// Compare current with previous
// and update previous.
if ($curr_count >= $prev_count)
return false;
$prev_count = $curr_count;
}
return true;
}
// Driver code
$n = 10;
if (areSetBitsIncreasing($n))
echo "Yes";
else
echo "No";
// This code is contributed by anuj_67
?>
Javascript
<script>
// Javascript program to check if counts of
// consecutive 1s are increasing order.
// Returns true if n has counts of
// consecutive 1's are increasing
// order.
function areSetBitsIncreasing(n)
{
// Initialize previous count
var prev_count = Number.MAX_VALUE;
// We traverse bits from right to
// left and check if counts are
// decreasing order.
while (n > 0)
{
// Ignore 0s until we reach
// a set bit.
while (n > 0 && n % 2 == 0)
n = parseInt(n / 2);
// Count current set bits
var curr_count = 1;
while (n > 0 && n % 2 == 1)
{
n = n / 2;
curr_count++;
}
// Compare current with previous
// and update previous.
if (curr_count >= prev_count)
return false;
prev_count = curr_count;
}
return true;
}
// Driver code
var n = 10;
if (areSetBitsIncreasing(n))
document.write("Yes");
else
document.write("No");
// This code is contributed by Rajput-Ji
</script>
Producción :
No
Complejidad del tiempo: O(log 2 n)
Espacio Auxiliar: O(1)
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA